Pattern 5: Kadane
The largest subarray problem looks like it asks for brute force — there are O(n²) candidates! Kadane solves it in a single pass with one local decision: extend what I'm carrying, or start over from scratch?
Try it first: Maximum Subarray
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Find the contiguous subarray (at least one element) with the largest sum and return that sum. The array may contain negative numbers.
Example: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (the subarray [4, -1, 2, 1]).
Did you try? Testing every subarray is O(n²) (or O(n³) if you re-sum each one). What blocks you: it seems you need to consider every possible start and every possible end. The theory below shows the turning point — asking only "what's the best subarray that ends here?" — which solves everything in a single pass.
The theory: the idea that unlocks everything
"Find the contiguous subarray with the largest sum" (with negatives in the middle — otherwise the answer would be the whole array, remember the sliding window lesson?).
The brute force tests every pair (start, end): O(n²) subarrays. The waste: subarrays that share the same ending are recomputed as strangers.
Kadane's insight is to change the question. Instead of "what's the best subarray?" (global, hard), ask: "what's the best subarray that ENDS exactly here, at position i?" (local, easy). Why? Because that version has a one-line recurrence:
best_ending_at(i) = max(
nums[i], ← start over here
best_ending_at(i-1) + nums[i] ← extend the previous one
)
The human reading: arriving at position i, I carry the best sequence that came
from behind. If that baggage is positive, it helps me — I extend. If it's
negative, it only gets in the way — I drop everything and start over at
nums[i].
And the final leap: every subarray ends at some position. So the global
answer is the maximum among all the best_ending_at(i) — which we collect
during the very same pass. Two accumulators and that's it:
current = best sum ending HERE
best = best sum seen ANYWHERE
Why is this correct? (the two-line proof)
The best subarray ending at i either has size 1 (just nums[i]), or it's an
extension of the best one that ended at i-1 — there's no third option, since
subarrays are contiguous. The max in the recurrence considers both. And since
every subarray ends at some i, sweeping all i covers all candidates.
Nothing escaped.
The signals in the statement
- "Largest/smallest contiguous subarray" (sum, product...) — especially with negative numbers, where sliding window breaks.
- The answer at each position depends only on the answer at the previous position.
- (Spoiler from the future: this recurrence is Dynamic Programming in its purest state — Kadane is your first DP lesson without you knowing it.)
Example 1 — Maximum Subarray
The classic [-2, 1, -3, 4, -1, 2, 1, -5, 4] (answer: 6, from the subarray
[4, -1, 2, 1]). Follow the two accumulators — notice current
starting over when the baggage goes negative, and best holding the record:
Why is it O(n)?
A single pass (n iterations) and, per iteration, two max — O(1) work. Total
O(n) time and O(1) space (two accumulators). The pairwise brute force
costs O(n²) — and with the sum recomputed inside, O(n³).
| Solution | Time | Space | Why |
|---|---|---|---|
| Brute force (all pairs + re-sum) | O(n³) | O(1) | n² subarrays × O(n) to sum |
| Brute force with incremental sum | O(n²) | O(1) | n² subarrays × O(1) |
| Kadane | O(n) | O(1) | 1 pass, local O(1) decision |
Example 2 — Maximum Product Subarray (the pattern put to the test)
Same statement, swapping sum for product: [2, 3, -2, 4] → answer 6.
Does Kadane work directly? Almost — but the product has a catch that the sum
doesn't: two negatives multiply into a positive. The worst product carried
so far (very negative) can become the best in the next step, if nums[i]
is negative.
The adaptation: carry two accumulators instead of one — the best AND the worst product ending here:
Test the third case by hand: in [-2, 3, -4], the worst product up to the 3 is
-6... which multiplied by -4 explodes to 24. Carrying the worst case is what
allows the best case to exist. The complexity doesn't change: a single pass,
O(1) per iteration → O(n).
The generalization lesson: the pattern isn't "the Kadane formula" — it's "define the best state ending at i and derive it from the state at i-1". Changed the operation? Rethink which states you need to carry (in the product: two).
🧠 Review quiz
0/41. What is Kadane's local decision at each position i?
2. Why does looking only at the 'best subarrays ending at each i' miss no candidate?
3. In Maximum PRODUCT Subarray, why also carry the WORST product ending at i?
4. Kadane is O(n) with negatives in the array. Why can't sliding window achieve the same in this problem?
Summary
- Kadane swaps the global question for the local one: best subarray ending here = max(start over, extend).
- Correct because every subarray ends somewhere — sweeping the endings covers everything.
- O(n)/O(1): a single pass, O(1) decision, two accumulators.
- In the product, carry best and worst (negatives redeem themselves).
- It's the gateway to Dynamic Programming — you'll meet it again there.
Last stop before the exam: the synthesis — the decision tree that picks the right pattern for any new statement.