PROBLEM LINK:
Author: Adabelle Xie
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, specifically Kadane’s algorithm.
PROBLEM:
Given an array of integers, return the maximum sum of consecutive elements from the array.
QUICK EXPLANATION:
Use Kadane’s algorithm. Keep track of two variables: max and current. For each element in the array, add it to current. If current becomes negative because of this, set it to 0. If current is greater than max, set max equal to current. After going through all the elements in the array, return max.
EXPLANATION:
If all the elements were positive or zero, the maximum sum would include all elements. However, elements in the array can be negative. This means that sometimes we will stop our sum when we encounter a negative number. Other times, including negative numbers is beneficial because positive numbers later in the array result in a net gain from continuing the sum. But if the current sum at any point is negative, we might as well have not included those numbers in the first place and started our sum after the current element. We keep track of the maximum sum we have discovered, and return it after processing all the array elements.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.