As part of my somewhat regular programming practice, I’ve recently looked at the maximum subarray problem. Basically, the problem goes like this: given an array of $N$ integers, find the greatest sum of contiguous elements. According to Wikipedia, the problem was first posed in 1977, with a solution of $O(N \log N)$. A linear-time algorithm was proposed soon thereafter, in 1984. The goal for the practice exercise was to come up with a linear-time algorithm, from scratch.
To get the ball rolling, if often helps to think of sub-optimal solutions.
There’s an obvious
$O(N^3)$ solution that’s fairly easy to come up with:
Why is it
Well, the outer loop gets executed for exactly $N$ elements.
The inner loop gets executed for $N-1$ elements the first time, $N-2$ elements the second time, and so on.
The inner loop also contains a sum that takes linear time to calculate.
The overall complexity of the solution is therefore $O(N \times N \times N)$.
Obviously, we can do better than this. In particular, instead of calculating the sum for each iteration of the inner loop, we can build it up incrementally.
Since we’ve replaced the linear-time sum calculation with a pair of constant-time operations, the complexity of this solution is now
It’s still not linear, but it’s better than what we started with.
So, how about the linear solution?
The solution I first came up with applied the same trick that we used to go from
$O(N^2)$ - modify the sum incrementally.
First, build the sum up incrementally - while it’s positive, continue adding elements to the end of the subarray, and keep track of the maximum so far.
If the sum becomes negative, then remove elements from the front of the subarray.
Here’s the full solution:
Enter some integers:
Max consecutive sum is:
In the end, all this is more complicated than it really needs to be. It turns out the solution is even simpler than that. It’s known as Kadane’s Algorithm, and looks like this:
The main difference with my solution is what happens once the current sum becomes negative. My solution shrinks the array one by one, in an attempt to make the sum positive again. This attempt is in vain, since removing an element from the subarray will only increase the sum if the removed element was negative. If the element is positive, then removing it will actually decrease the sum, which hardly helps. Kadane’s algorithm realizes this and resets the sum to zero, effectively discarding the subarray completely.
For a more detailed write-up, see Programming Pearls: Algorithm Design Techniques by Jon Bentley et al. The article is more than 30 years old, but worth the read if you’ve got access to it.