Maximum Subarray Sum (Kadane's Algorithm)
WHAT IT SAYS
Find the largest sum obtainable from any contiguous subarray of the array.
WHAT IT'S REALLY ASKING
"You are never really choosing a subarray. At each element you are answering one question: is the sum I've been carrying an asset I should keep, or a debt I should default on?"
Try every subarray
O(n^3) time, O(1) space (O(n^2) if you keep a running sum)Two nested loops pick a start and an end, an inner loop adds up everything between them, and you keep the largest total you ever see. Correct by construction — you literally look at every candidate.
WHERE THE WORK IS WASTED — Neighbouring subarrays share almost all of their work. sum(2..7) and sum(2..8) differ by exactly one number, yet the inner loop walks from index 2 again as if it had never seen those elements. Worse, the loops keep re-examining subarrays whose fate was already sealed: once the stretch 2..7 has added up to -40, every subarray starting at 2 and ending past 7 is dragging that -40 along, and the algorithm cheerfully recomputes it for each one.
A negative running sum is dead weight, never a foundation.
Collapse the search. Instead of asking 'what is the best subarray?', ask the smaller question 'what is the best subarray that ends exactly at index i?' There are only n such questions, and every subarray is the answer to exactly one of them — so the global answer is just the best of the n local answers. Now look at a single local question. The best subarray ending at i either (a) contains i-1 too, or (b) starts at i. There is no third case. Case (a) is worth best_ending_at(i-1) + a[i]; case (b) is worth a[i]. So you take the max of the two — the past is a single number, and it either helps or it doesn't. And notice when it doesn't. If best_ending_at(i-1) is negative, then prefixing it to anything makes that thing strictly smaller. Not smaller in a way you might recoup later — strictly, permanently smaller, because the sum is already banked and no future element can un-add it. So a negative carried sum is not a weak start, it is a liability you drop instantly, and the answer at i is a[i] alone. That's an exchange argument: given any optimal subarray whose prefix sums to a negative number, deleting that prefix yields a subarray that is at least as good. So an optimal subarray never begins with a negative-sum prefix — and you can safely reset the moment your running total goes under zero.
One number, one pass
O(n) time, O(1) space, one passWalk the array carrying a single running sum. Add the current element; if the running sum goes negative, throw it away and start fresh from the next element. Track the largest running sum you ever held — that's the answer. If you also need the indices, remember where the current run started and snapshot it whenever the best is beaten.
Best-Ending-Here
YOU'LL SEE IT AGAIN WHEN
- The search space is every contiguous stretch of a sequence, and neighbouring stretches overlap almost entirely.
- The value of a stretch is built incrementally, so extending by one element only needs the previous total — not the elements inside it.
- There's a point where carrying history is strictly worse than abandoning it, meaning the past is summarisable as a single 'is it worth keeping' number.