What is Kadane's algorithm?
Kadane's algorithm finds the maximum sum of any contiguous subarray in a single O(n) pass. It tracks one
running value — the best sum ending exactly at the current position — and at every step that value either
extends the run before it or restarts fresh at the current element, whichever is bigger.
The final answer is just the largest running value seen across the whole walk.
- Running sum
- The best sum of a subarray that ends exactly at the current index
- Extend
- Add the current element onto the running sum, because it's still worth carrying forward
- Restart
- Drop the running sum and start fresh at the current element, because it's gone negative
Why Kadane's at all?
Picture tracking a running profit-and-loss streak, day by day. Each day you add that day's number to your running total. The moment the running total dips negative, dragging that negative baggage into tomorrow can only hurt — you're strictly better off starting fresh from tomorrow's number alone.
Kadane's algorithm is exactly that instinct made precise: one running value, one comparison per step, and a record of the best the running value ever reached.
Every day only adds — the running total never has a reason to drop here.
What does the running decision look like?
The same extend-or-restart choice plays out differently depending on the array. Watch what happens the moment the running sum turns negative, and what happens when every value is negative to begin with.
Track the best sum ending here
At each index, compare extending the running sum against restarting at just this element. Keep whichever is bigger, and remember the best running value seen so far — that's the answer.
The best run keeps shifting until [4, -1, 2, 1] settles in as the winner: 6.
The moment the running sum goes negative
The running sum doesn't have to restart the instant it dips negative — it restarts the instant extending would lose to starting fresh. Watch the sum turn negative first, then get dropped.
Negative baggage gets left behind — the run restarts at 5 and climbs to a new best of 8.
When every value is negative
There's no "0 or better" fallback here — every subarray must keep at least one element. Restarting still happens, but the best-so-far can, and should, stay negative.
The best possible answer is -1. Flooring it at 0 would be flat-out wrong.
Two decisions
Underneath, every step makes exactly one of two moves: carry the run forward, or throw it away and begin again right here. Nothing else ever happens.
Extend
Add the current element onto the running sum. This wins whenever the running sum so far is still zero or positive — carrying it forward can only help.
Nothing here is worth throwing away — the run only ever grows.
function maxSubArray(nums: number[]): number {
let runningSum = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
// Extend if the run is still worth carrying, otherwise restart here.
runningSum = Math.max(nums[i], runningSum + nums[i]);
best = Math.max(best, runningSum);
}
return best;
}
Restart
Drop the running sum and start over at the current element. This wins whenever the running sum has gone negative — extending a negative run can only ever drag the next value down.
-9 turns the run negative — 6 alone beats dragging that negative run forward.
function maxSubArrayAllowsNegative(nums: number[]): number {
// Seed from the first element — never from 0. A subarray must have
// at least one element, and the true answer can be negative.
let runningSum = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
runningSum = Math.max(nums[i], runningSum + nums[i]);
best = Math.max(best, runningSum);
}
return best;
}
Where it works — and where it breaks
Kadane's algorithm leans on one quiet assumption: the running sum is always seeded from a real element, never from an empty subarray. Get that wrong and an all-negative array silently produces the wrong answer.
Works when negative dips get carried through, not erased
The running sum is allowed to go negative for a step or two — it only gets thrown away once extending it would actually lose to restarting. Extend, extend, keep the record.
-4 never beats extending. The whole array turns out to be the best subarray: 10.
Breaks when you floor the running sum at 0
A common bug resets the running sum to 0 the instant it goes negative, treating 0 as a safe fallback. On an all-negative array, that produces 0 — which isn't even a valid subarray sum here.
The correct answer is -2. Flooring at 0 would report an answer that was never achievable.