Kadane's algorithm
mediumIs the run so far helping or hurting? If it has gone negative it can only drag down whatever follows, so discard it. That single comparison is the whole algorithm - and it is dynamic programming in disguise.
O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How kadane's algorithm works
current is the best sum of a subarray ending exactly at the current index. Extending it with a[i] is worth current + a[i]; abandoning it and restarting is worth a[i] alone. Take whichever is larger. The comparison only prefers restarting when current is negative - a negative run can only drag down whatever follows, so it is dead weight.
This is dynamic programming in disguise. The recurrence is dp[i] = max(a[i], dp[i-1] + a[i]), and since each state needs only the previous one, the table collapses to the single variable current - O(1) space. best simply records the largest state ever seen. Spotting the DP is what lets the idea generalise beyond plain sums.
The brute force enumerates all n(n+1)/2 subarrays - 45 of them on a nine-element array - and stays O(n²) even with running sums. Kadane reads each element once and makes two comparisons: extend-or-restart, then a best check. Recognition: a maximum or minimum over contiguous runs, where a losing streak can be cut loose the moment it turns negative.
Step by step
- Take -2, 1, -3, 4, -1, 2, 1, -5, 4. Start with current = best = a[0] = -2.
- At 1: extending gives -2 + 1 = -1, restarting gives 1. Restart - current = 1, best = 1.
- At -3: extending gives -2, restarting gives -3. Extend, barely - current = -2, best stays 1.
- At 4: extending gives 2, restarting gives 4. The old run is dead weight - restart with current = 4, best = 4.
- The next values -1, 2, 1 all extend: current runs 3, 5, 6, and best climbs with it to 6.
- At -5, current falls to 1; the final 4 lifts it back to 5. Neither move threatens 6.
- Answer: 6, from a[3..6] = 4, -1, 2, 1. One pass, where the brute force would have tested 45 subarrays.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) |
Reference implementation
Python
def max_subarray(a):
"""Largest sum of any contiguous subarray, in one pass."""
best = current = a[0]
for x in a[1:]:
current = max(x, current + x) # extend, or restart here
best = max(best, current)
return bestJavaScript
function maxSubarray(a) {
let best = a[0], current = a[0];
for (let i = 1; i < a.length; i++) {
current = Math.max(a[i], current + a[i]); // extend or restart
best = Math.max(best, current);
}
return best;
}Java
static int maxSubarray(int[] a) {
int best = a[0], current = a[0];
for (int i = 1; i < a.length; i++) {
current = Math.max(a[i], current + a[i]);
best = Math.max(best, current);
}
return best;
}Worth noticing
One decision, repeated n times
At every position: is the run so far helping or hurting? If `current` has gone negative it can only drag down whatever follows, so throw it away and start again at a[i]. That single comparison is the entire algorithm.
It is dynamic programming in disguise
`current` is 'the best subarray ending exactly here'. That is a DP state, and the recurrence is dp[i] = max(a[i], dp[i−1] + a[i]). Because dp[i] only needs dp[i−1], the table collapses to one variable - O(1) space.
Initialising to 0 is the classic bug
Start `best` at 0 and an all-negative array returns 0, which is not a subarray at all. Starting at a[0] handles it correctly - and interviewers test exactly this case.
Common pitfalls
- Initialising best or current to 0. An all-negative array then answers 0 - the sum of no subarray at all. Start both at a[0].
- Updating best before current at each index. The order is extend-or-restart first, then compare - reversed, the run ending at the last element can never win.
- Assuming an empty subarray is allowed. This variant requires a non-empty one - which is exactly why it starts from a[0] rather than from 0.
- Returning only the sum when the interviewer wants the subarray. Track a start index: reset it on every restart, snapshot the range whenever best improves.
Where it is used
- Maximum subarray sum - LeetCode 53 verbatim, and a fixture of first-round interviews.
- Best time to buy and sell stock with one transaction: run Kadane on the day-to-day price differences.
- Maximum sum of a circular subarray: combine Kadane's answer with the total minus the minimum subarray.
- Maximum-sum submatrix in 2-D: fix a pair of rows, collapse each column to a sum, run Kadane across them.
Frequently asked questions
What are the time and space complexity of Kadane's algorithm?
O(n) time - a single pass with two comparisons per element: extend-or-restart, then the best check. O(1) space - just current and best, since each state depends only on the previous one. The brute-force alternative examines all n(n+1)/2 subarrays, O(n²) at best.
Why is it safe to discard a negative running sum?
current + a[i] beats a[i] exactly when current is positive. Once current goes negative, it subtracts from every subarray that would carry it forward, so no optimal subarray begins with that prefix attached. Cutting it loose can only help - and that observation is the entire proof.
Does Kadane's algorithm work when all numbers are negative?
Yes, in this form. current = max(a[i], current + a[i]) restarts at every element, so best ends up as the largest single element - the correct answer, since any longer subarray only sums lower. The version that breaks is the one initialised to 0.
How is Kadane's algorithm dynamic programming?
Define dp[i] as the best sum of a subarray ending at i. The recurrence dp[i] = max(a[i], dp[i-1] + a[i]) has optimal substructure, and because only dp[i-1] is ever needed, the table collapses to one variable. Kadane is that DP with the table optimised away.