Sequence Optimization
Decide at every value whether to extend the current run or start fresh.
The idea
Kadane's algorithm compresses a contiguous-range dynamic program into the best state ending at the current index. The central decision is local: keep the previous run or reset at the current value.
The same idea extends to circular sums by tracking a minimum run to exclude, and to products by retaining both the highest and lowest products because signs can flip their roles.
Carry a running score down a row of checkpoints. Keep the score while it helps; drop it and restart when the current checkpoint is stronger alone.
When to reach for it
- The answer must use a contiguous range.
- A best state ending at one index determines the next state.
- You need a linear scan with constant extra space.
Language-independent template
current = best = nums[0]
for value in nums[1:]:
current = better(value, extend(current, value))
best = better(best, current)
return bestComplexity — time O(n), space O(1).
Common mistakes
- Resetting to zero and breaking all-negative inputs.
- Forgetting the minimum product that a negative value can flip.
- Using total minus minimum for an all-negative circular array.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Find the contiguous subarray with the largest sum.
Find the best subarray when the array wraps around.
Find the contiguous subarray with the largest product.