Kadane's, derived from scratch in four lines

Maximum Subarray is the canonical “I memorized it, then blanked on it” problem. The fix isn’t better memorization — it’s deriving the recurrence from a framing so natural you can rebuild it cold.

The framing that does all the work

Ask one question: what’s the best subarray that ends exactly at index i?

Call it end_here[i]. Every subarray ends somewhere, so the global answer is just the best of these: max(end_here). That’s the whole decomposition — no clever insight required yet.

Now the recurrence writes itself. A subarray ending at i either extends the best subarray ending at i-1, or it starts fresh at i. There is no third option — that’s what “contiguous” means:

end_here[i] = max(end_here[i - 1] + nums[i], nums[i])

When does starting fresh win? Exactly when end_here[i-1] is negative — a negative prefix can only drag you down, so you drop it. People memorize “reset when the running sum goes negative” as a trick; it’s not a trick, it’s the max doing its job.

Collapsing to four lines

end_here[i] only ever looks at end_here[i-1], so the array collapses to a single variable:

def max_subarray(nums):
    cur = best = nums[0]
    for n in nums[1:]:
        cur = max(cur + n, n)
        best = max(best, cur)
    return best

O(n) time, O(1) space, and every line traces back to a sentence you can say out loud: cur is the best subarray ending here; best is the best seen anywhere; extend or restart, whichever is larger.

Why this survives the follow-ups

Because the derivation generalizes and the memorized line doesn’t:

• “Return the subarray itself.” Track the start index — reset it whenever restarting wins the max.
• “All negatives?” Already handled: initializing from nums[0] (not 0) means the answer is the least-negative element. If you memorized cur = max(cur, 0)-style variants, this is where they break.
• “Maximum product subarray?” Same framing, but a negative × negative flips sign — so you carry the best and worst product ending here. The “ending at i” decomposition is doing the heavy lifting; only the state widens.

Coach’s note · On your next review, don’t start with the code. Start by defining end_here[i] in one sentence. If the sentence is right, the four lines are inevitable.