Kadane's Algorithm
Kadane's algorithm answers a deceptively hard question in one pass: which run of neighbouring values has the biggest sum? Brute force checks every possible run - O(n²) of them. Kadane walks the array once with a single insight: the best run ending at position i either extends the best run ending at i−1, or starts fresh. Nothing else is possible. It is dynamic programming shrunk to two variables, and a favorite interview question ("maximum subarray").
Watch the pass
Press play - or drag the timeline and step through it yourself.| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| value | 4 | -2 | 7 | -9 | 3 | 5 | -1 | 2 | -6 | 4 |
| best run ending here | · | · | · | · | · | · | · | · | · | · |
| best so far | · | · | · | · | · | · | · | · | · | · |
Find the run of neighbouring values with the biggest sum. Rule: the best run ending at position i either extends the previous run - or starts fresh at i.
Complexity
A gambler's running streak
You track daily wins and losses: +4, −2, +7, −9... You want to know your best streak ever. Walking through the days, you keep one number: how much the current streak is worth. Each day you ask one question: is my streak so far actually helping me, or is it dead weight? If the streak total ever drops below zero, carrying it forward can only hurt - so you forget it and start counting fresh from today. The best value your counter ever reaches is the answer.
How it works, step by step
Walk the array once, keeping two numbers: the best run ending right here, and the best run seen anywhere so far.
At each new value, the run ending here has only two options: the previous run plus this value, or this value alone. Take whichever is bigger.
That comparison has a simple meaning: if the previous run's total is negative, it is dead weight - drop it and start fresh.
Update the best-so-far if the run ending here beats it.
At the end, best-so-far is the answer. One pass, two variables - O(n) time, O(1) space.
Why it works: every possible run ends *somewhere*. By computing the best run ending at each position, no candidate is ever missed.
The code, in JavaScript
The whole algorithm. Two variables, one loop, one decision per value: extend the run or start fresh.
function maxSubarraySum(arr) {
let endingHere = arr[0]; // best run that ends at this position
let best = arr[0]; // best run seen anywhere
for (let i = 1; i < arr.length; i++) {
// Extend the run - or start fresh if the run is dead weight.
endingHere = Math.max(arr[i], endingHere + arr[i]);
best = Math.max(best, endingHere);
}
return best;
}
maxSubarraySum([4, -2, 7, -9, 3, 5, -1, 2, -6, 4]); // → 9
maxSubarraySum([-3, -1, -4]); // → -1 (least bad)Dry run: the best run in [4, -2, 7, -9, 3, 5, -1, 2, -6, 4]
The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.
| Step | Position | What happened |
|---|---|---|
| 1 | 1 | Position 1: only one option - the run is just 4. |
| 2 | 2 | Position 2: extend the run (4 + -2 = 2) - better than starting fresh at -2. |
| 3 | 3 | Position 3: extend the run (2 + 7 = 9) - better than starting fresh at 7. |
| 4 | 4 | Position 4: extend the run (9 + -9 = 0) - better than starting fresh at -9. |
| 5 | 5 | Position 5: extend the run (0 + 3 = 3) - better than starting fresh at 3. |
| 6 | 6 | Position 6: extend the run (3 + 5 = 8) - better than starting fresh at 5. |
| 7 | 7 | Position 7: extend the run (8 + -1 = 7) - better than starting fresh at -1. |
| 8 | 8 | Position 8: extend the run (7 + 2 = 9) - better than starting fresh at 2. |
| 9 | 9 | Position 9: extend the run (9 + -6 = 3) - better than starting fresh at -6. |
| 10 | 10 | Position 10: extend the run (3 + 4 = 7) - better than starting fresh at 4. |
Good choice when…
- The question is about the best contiguous run: max subarray sum, best trading window (prices → daily deltas), quietest stretch (negate and maximize).
- You get one pass over a stream and cannot store it - Kadane needs only two numbers of state.
- As the simplest real example of DP space-shrinking: the dp array collapses to a variable because each entry reads only the previous one.
Bad choice when…
- The values are all positive - the answer is trivially the whole array; you need no algorithm.
- You need the best subsequence (gaps allowed) - that is just "sum of positives", a different and easier question.
- The window has a size limit ("best run of at most k") - plain Kadane cannot enforce length; use sliding window or prefix sums with a deque.
Common mistakes
- All-negative arrays are the classic breaker: initializing `best = 0` returns 0 - the sum of an *empty* run - instead of the least-bad value. Initialize both variables with arr[0] and start the loop at 1.
- `Math.max(arr[i], endingHere + arr[i])` and "reset when the running sum goes negative" are the same rule written two ways - but mixing both forms in one implementation double-resets and quietly skips valid runs.
- Kadane finds one best run. If two runs tie, which one you get depends on `>` vs `>=` when updating - decide deliberately if the caller cares.
- For "best time to buy and sell a stock", run Kadane on the day-to-day *differences*, not the prices - a subtle mapping that interviewers expect you to spot.
Kadane's Algorithm vs. its closest relatives
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Kadane's Algorithmthis page | O(n) | O(n) | O(n) | O(1) | - |
| Sliding Window | O(n) | O(n) | O(n) | O(k) | - |
| Fibonacci: Memo vs Tabulation | O(n) | O(n) | O(n) | O(n) | - |
| Two Pointers | O(n) | O(n) | O(n) | O(1) | - |