On this page
Description
Kadane's algorithm finds the contiguous subarray with the largest sum in one pass. At each element it asks one question: is it better to extend the run that ends just before me, or to start fresh here? Then it keeps the best answer seen so far. It's the smallest dynamic-programming problem you'll meet. The same scan finds the best stretch in any series, such as the biggest gain in a price history or the worst run of slow responses.
We'll go from simple to more technical:
- The pattern: the best sum ending here, and the best so far.
- Where the same scan shows up in production time series.
- The edge cases: all-negative arrays, empty input, sum versus the subarray itself.
- Where it stops: two dimensions, and other variants.
The approach
Checking every subarray works, but it's O(n^2): each start index adds up a growing range again. Kadane's keeps two numbers instead. bestEndingHere is the best sum of a run that ends at the current element. best is the best sum seen anywhere. At each element, either add it to the run or start a new run with it, whichever is larger. A run whose sum has gone negative can only drag the next element down, so that's when it restarts.
For [3, -5, 4, -1, 2, -6, 1]:
| Element | Extend or restart? | Best ending here | Best so far |
|---|---|---|---|
| 3 | start | 3 | 3 |
| -5 | extend: 3 - 5 = -2 | -2 | 3 |
| 4 | restart: 4 beats -2 + 4 | 4 | 4 |
| -1 | extend: 4 - 1 = 3 | 3 | 4 |
| 2 | extend: 3 + 2 = 5 | 5 | 5 |
| -6 | extend: 5 - 6 = -1 | -1 | 5 |
| 1 | restart: 1 beats -1 + 1 | 1 | 5 |
The answer is 5, from [4, -1, 2].
Java
int bestEndingHere = nums[0];
int best = nums[0];
for (int i = 1; i < nums.length; i++) {
bestEndingHere = Math.max(nums[i], bestEndingHere + nums[i]);
best = Math.max(best, bestEndingHere);
}
Python
best_ending_here = best = nums[0]
for x in nums[1:]:
best_ending_here = max(x, best_ending_here + x)
best = max(best, best_ending_here)
This is dynamic programming in its smallest form. The best run ending at index i depends only on the best run ending at index i - 1. So the whole table shrinks to one variable.
Where you'll see it
"Find the best or worst stretch" comes up with any time series. The largest drop in an account balance is one. Another is the worst stretch of slow responses, measured as the time window with the most total latency over the target. Both are the same scan.
Which tool for which job?
| You need | Use |
|---|---|
| The largest contiguous sum | Kadane's: extend or restart |
| The smallest contiguous sum | Kadane's with min |
| The largest sum when the array wraps around | max(Kadane, total - smallest sum) |
| The largest contiguous product | track the max and the min ending here |
| The best buy-then-sell profit | Kadane's on day-to-day differences |
| The largest-sum rectangle in a matrix | fix two rows, collapse, run Kadane's - O(rows^2 * cols) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Starting best at 0 | an all-negative array reports 0 | start from nums[0] |
Starting from nums[0] with no empty check | an exception stands in for a decision | reject empty input, or return an empty optional |
| Returning the sum when the subarray was asked for | the wrong answer to the question | track where the current run started |
Updating best before bestEndingHere | the newest element is ignored | update the run first, then the best |
| Expecting it to work on products | sign flips are missed | track the max and the min |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Kadane's starts with best = 0 instead of nums[0]. What breaks, and on which inputs?
Show answer
An all-negative array returns 0, but no subarray of it sums to 0. The right answer is its largest single element, such as -1 for [-3, -1, -4]. Starting from 0 makes every real answer look worse than a made-up one.
2. Why is Kadane's called the simplest dynamic-programming problem?
Show answer
The best run ending at index i depends only on the best run ending at index i - 1, plus nums[i]. Only the previous answer is ever needed again, so the DP table shrinks to one running variable.
3. A solution returns the right maximum sum. Now it must return the subarray itself. Is that the same work?
Show answer
No. The sum needs two running numbers. The subarray also needs the start of the current run, updated whenever the run restarts, and the start and end of the best run, saved whenever a new best appears. A correct sum doesn't prove the index bookkeeping is correct.
Key takeaways
- At each element, extend the current run or restart from the element, whichever is larger. That's the whole O(n) idea.
- Start both values at
nums[0], not 0, or an all-negative array returns 0. - The best run ending at i depends only on the best run ending at i - 1, so the DP table is one variable.
- Returning the subarray needs extra index tracking beyond the sum.
- The 2D version (the best rectangle) runs Kadane's once per pair of rows: O(rows^2 * cols).