IntermediateGreedy & Intervals
Kadane's algorithm: the best subarray
At each number, either extend the run you're on or start fresh from here, whichever is bigger. One pass finds the max subarray.
The idea
A subarray ending at i either continues the best subarray ending at i − 1 or starts at i. If the running sum went negative, it only drags the next number down, so start over.
Track the best sum seen at any point.
Worked example
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
- -2 → 1 (restart) → -2 (1 − 3) → 4 (restart) → 3 → 5 → 6 → 1 → 5
- The best seen is 6, from [4, -1, 2, 1].
In code (Python)
def max_subarray(nums):
current = best = nums[0]
for x in nums[1:]:
current = max(x, current + x) # extend or start over
best = max(best, current)
return bestO(n) time, O(1) space.
How to spot it
- “maximum sum subarray”, best profit over a stretch, variations with products (track min too).
Common mistakes
- Starting with 0, which is wrong when every number is negative.
- For products, forgetting a negative times a negative can become the max.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →