Carry history or start fresh: Kadane in one decision

Maximum-subarray gets taught as a clever trick with a name attached. I'd rather strip the name off and look at the only thing that does work: a single per-element decision. This is a sibling to solving everything with DP — Kadane is what DP collapses to when the state at each step is one number and the choice is binary.

The one decision

Stand at index i with a running subarray ending just before it. You have two moves and exactly two:

• Extend: append nums[i] to what you've been building. The sum becomes cur + nums[i].
• Abandon: throw away everything behind you and let nums[i] be a fresh start. The sum becomes nums[i].

You want the larger of the two ending here, so:

cur = max(nums[i], cur + nums[i])
best = max(best, cur)  // the answer can end at any index, so track it separately

The restart is not a special case you handle. It falls out of the max. If cur went negative, then cur + nums[i] < nums[i], and the max picks nums[i] — you've started fresh without writing an if. A negative prefix is dead weight; carrying it can only drag the next sum down, so the algorithm drops it the instant it stops helping. That single line is the whole algorithm. best exists only because the best subarray can end anywhere, not necessarily at the last index.

Worth noticing when Kadane even earns its keep: if every number is positive, extending is always better than abandoning, so the answer is trivially the whole array. The decision only becomes interesting once negatives are in the mix — they're what make "should I keep carrying this?" a real question.

Trace it by hand

Hand-tracing is what made this click for me; the one-liner reads as obvious only after you've watched it restart. Take [-2, 1, -3, 4, -1, 2, 1, -5, 4].

i   nums[i]   cur + nums[i]   cur = max(nums[i], cur+nums[i])   best
0    -2        —              -2                                 -2
1     1        -1             1   (abandon: -1 < 1)              1
2    -3        -2             -2  (extend: still > -3)           1
3     4         2             4   (abandon: 2 < 4)               4
4    -1         3             3                                  4
5     2         5             5                                  5
6     1         6             6                                  6
7    -5         1             1                                  6
8     4         5             5                                  6

Two restarts, at i=1 and i=3, both exactly where the running sum had gone non-positive and the element alone was the better bet. Answer 6, the subarray [4, -1, 2, 1]. The cur column is the decision log; best just remembers the high-water mark.

Why not a sliding window?

This is the question I find most useful to sit with, because answering it teaches both patterns by negative space. A window slides — it advances a left pointer to shrink. So when a running sum drops, the window's only available move is "drop the leftmost element." Kadane's move, by contrast, is "drop everything behind me." Those are not the same move, and the difference is the whole story.

Here's the probe. Two arrays produce the same symptom — the running sum just dropped — but demand opposite fixes:

A window can only do the first. When the dead weight sits in the middle of your best run, shrinking from the left throws away the good prefix 3 while keeping the rot. The correct response — abandon the whole prefix and start at 4 — is a move a window structurally cannot make.

This is the sliding window post's monotonicity point seen from the other side. A window is legal only when the tracked quantity moves in one direction as the window grows, so a sagging sum unambiguously means "shrink." With negatives mixed in, the sum is not monotonic in window growth: the same symptom maps to two opposite correct actions depending on where the bad element is. No consistent shrink rule exists, so no window can be correct. Kadane sidesteps the whole problem by never shrinking — it only ever extends or resets to zero history.

The idea is broader than the name

I used to wonder whether maximum-subarray was the only place this trick lived. It isn't — the name is narrow, the lens is broad. The transferable question is: at each step, does carrying history help, or should I start fresh? Once you hold it that way, the same decision shows up wearing different clothes.

1. Maximum product subarray
   Same carry-or-restart decision, but a negative number flips max and min — a huge negative product becomes a huge positive one the moment you multiply by another negative. So you track both the running max and the running min ending here, because today's smallest could be tomorrow's largest. The decision is identical; the state just doubled.
2. Best time to buy and sell stock
   Walk the prices tracking the lowest seen so far. At each day you decide: is this price a better fresh start (a lower buy) than the one I'm holding? If so, reset the buy point. It's "abandon the carried history when a better starting point appears" — Kadane's restart in a different costume.

The connection to DP as recursion with a cache is exact: Kadane is the degenerate case where the optimal solution ending at i depends only on the optimal solution ending at i-1, through one binary choice. No table, because the only state worth remembering is a single previous number. That's why it reads as a loop and not a recurrence — the memo has one slot.

Problems to practice