Start from the brute force#
There are about n^2 / 2 subarrays. Summing each one is another factor of n, so the naive answer is O(n^3), and keeping a running sum makes it O(n^2). Both are too slow for an array of 200000 numbers, but they are worth thinking about for a moment because the fast solution is a compression of them.
One question per position#
Instead of asking about every subarray, ask a smaller question once per index:
What is the largest sum of a subarray that ends exactly here?
Call it best_ending_here. There are only two possibilities for that subarray. Either it is the single element a[i], or it is a[i] stuck on the end of the best subarray ending at i - 1. So:
best_ending_here = max(a[i], best_ending_here + a[i])
That is one comparison and one addition per element. Keep the largest value this has ever taken, and that is the answer.
Why the two cases are exhaustive#
Any subarray ending at i either has length 1, or it has something before a[i]. If it has something before, that something is itself a subarray ending at i - 1, and you would never want a worse one than the best. So carrying one number forward really does cover every case.
This is the shape of almost every dynamic programming solution: define an answer that ends at a position, work out how it relates to the one before, and keep only what you need.
The trap with negative numbers#
If every number is negative, the answer is the largest single element, not zero. Starting the running total at 0 quietly assumes an empty subarray is allowed, and on an all negative input it returns 0, which is wrong when the statement says the subarray must not be empty.
Start both values at a[0] and loop from index 1. That is the version that is right in both cases.
The cost#
- Time:
O(n), one pass. - Memory:
O(1), two numbers.
Where this shows up#
Maximum product subarray works the same way but needs two carried values, because a large negative times a negative becomes a large positive. Best time to buy and sell a stock is the same idea with a running minimum. Any time a question asks for the best contiguous run, ask what the best run ending here is.