Daily bit(e) of C++ | Maximum subarray sum
Daily bit(e) of C++ #168, Common interview problem: Maximum subarray sum.
Today we will look at a common C++ interview problem: Maximum subarray sum.
Given a non-empty array of integers, determine the maximum subarray sum, i.e. the maximum sum of consecutive elements.
For example, for the input {-1,1,2,-1,3,-2,1}, the maximum subarray sum is 5, achieved by summing up the subarray {1,2,-1,3}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/bd9d4Pj78.
Solution
The first observation is that to improve a sum, we want only to add positive numbers. However, there is a complication. A negative number can be part of a maximum sum if it has larger sums on either side, e.g. {1,2,-1,3}.
So let’s consider when we do not want to include a negative number in a sum. If we go left-to-right, it is exactly when the sum on the left is higher than the absolute value of this element. For example, if our current situation is {1,2,-4}, it doesn’t matter what comes next; we know that this portion of the array will not be able to contribute (the 1+2 can still be the overall maximum).
With that, we can construct a solution. Going left to right, we can keep track of the maximum subarray ending at that position. We can calculate the maximum subarray by adding the maximum subarray for the previous position to the current element; however, only if the previous maximum was positive.
