Maximum Subarray
How to find the best-scoring contiguous stretch of a list in one pass, without checking every possible stretch. (Kadane's algorithm — one running total, one decision per number.)
The job
You have a list of numbers — some positive, some negative. Find the contiguous stretch (no skipping) whose numbers add up to the largest total.
The obvious way
Try every possible start and end position, add up each stretch, and keep the biggest total.For 9 numbers that is on the order of 81 sums to compute.
The idea
Walk the list once, keeping a running total of "the best stretch that ends right here." If that running total ever goes negative, it can only drag down anything added after it — so throw it away and start a fresh stretch at the next number. Otherwise keep extending it.
Think of it like this. Checking your net mood across a week of ups and downs. If yesterday left you in a worse mood than starting fresh today would, you mentally write it off and start counting from today — you don't keep carrying a losing streak forward.
Tracking the best run so far
9 numbers, positive and negative. Find the contiguous stretch whose numbers add up to the largest total.
def max_subarray(nums):
best = cur = nums[0]
for i in range(1, len(nums)):
if cur < 0:
cur = nums[i]
else:
cur += nums[i]
best = max(best, cur)
return bestThis run
Best contiguous total is 6, from index 3 to 6 — found in one pass over 9 numbers instead of checking every stretch.
The names you just watched
cur (the running total)
The best total of a stretch that ends exactly at the number under the guide. It either grows by absorbing the next number, or gets discarded.
Reset, don't just clamp to zero
The moment `cur` is negative, no future stretch benefits from including it. Restarting at the next number is strictly better than dragging a losing total forward.
best is a separate number
`cur` can legally shrink or restart — it is not the answer. `best` only ever grows, recording the highest `cur` has reached at any point.
How to spot a Kadane's-shaped problem
The tell: You need the best contiguous run through a sequence, and a single running value can decide in O(1) whether to extend or restart at each step.
Reach for it when
- The phrase "contiguous subarray" or "contiguous stretch" appears.
- A brute-force answer is checking every (start, end) pair.
- The decision at each element only depends on the running total, not the whole history.
- Numbers can be negative — a purely additive greedy scan would otherwise be trivial.
Not this when
- The subsequence does not need to be contiguous (that is usually a different DP).
- You need the actual best K disjoint stretches, not just one — that needs extra state.
- The "best" combines values non-additively (max, product with unknown sign, etc.) without adapting the running value to match.
- Order does not matter, so any subset is allowed — sort and greedily pick instead.
Practice
6 problemsThe lesson, exactly. Keep two running numbers — the current stretch and the best stretch seen — and update both on every element.
Same reset-when-bad idea, but track a running MIN alongside the running MAX — a negative number can turn the worst product into the best one.
Run Kadane once for the normal max, once for the MIN subarray, then compare against total − min for the wrap-around case.
A DP where each state looks back at a bounded window and takes the best split — the same "extend or restart" instinct, generalized.
Precompute the best single window sliding from each direction, then combine — three Kadane-flavored passes, not one.
Kadane on the array repeated twice covers every wrap-around case; multiply by k only when the whole-array sum itself is positive.