Overview
Kadane's Algorithm finds the largest sum of any contiguous subarray in a single pass. The rule at its heart is one line: at each element, decide whether to extend the run you are on or abandon it and start fresh from here.
The insight that makes it correct is that a running sum which has gone negative can never help anything that comes after it. Whatever follows is strictly better off starting from zero. So the moment the running total drops below zero it gets discarded, and the algorithm never needs to look backwards — which is how an O(n³) brute force over all subarrays collapses to a single O(n) sweep with two variables.
How Kadane's Algorithm works
- Initialise both the running sum and the best sum to the first element — not to zero, which would break on all-negative input.
- Move to the next element and ask: is it larger on its own than it is added to the running sum?
- If it is, the previous run was dragging it down — drop the run and let the running sum become just this element.
- Otherwise extend: add the element to the running sum.
- Update the best sum if the running sum now exceeds it, and continue to the end of the array.
When to use it
- Finding the best window in a time series: peak profit stretch, worst drawdown, most productive interval.
- The maximum-subarray step inside the 2D version, where it runs once per pair of column boundaries.
- Signal and image processing, where the strongest contiguous response has to be located in one pass over streaming data.
- A standard demonstration that a greedy local decision can be provably optimal — unlike coin change, where it is not.
Complexity analysis
Time is O(n) with a single pass and no nested loop, and space is O(1) since only the running sum and the best sum are held. It is also an online algorithm: each element is consumed once and never revisited, so it works on a stream where the full array is never in memory. Recovering the actual subarray, rather than just its sum, costs two more integers for the start and end indices.
Frequently asked questions
What happens when every number is negative?
The answer should be the single least-negative element, and the algorithm returns it — provided you initialised with the first element rather than 0. Initialising to 0 makes it report 0, an empty subarray, which is the most common bug in this algorithm.
How do you recover the subarray itself?
Track a tentative start index that resets whenever the run restarts, and commit the start and end indices at the moment the best sum improves. It costs nothing asymptotically.
Does it extend to two dimensions?
Yes. Fix a pair of left and right column boundaries, compress each row between them into a single sum, and run Kadane down that compressed column. Over all column pairs this gives O(rows · cols²), which is still far better than brute force.