Maximum Subarray
Extend the running sum, or restart at the current element — whichever is larger.
Kadane Trace
Problem
Given an integer array, find the contiguous, non-empty subarray whose elements add up to the largest possible sum. Return that maximum sum, even when every number in the array is negative.
Examples
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Input: nums = [-8,-3,-6,-2,-5,-4]
Output: -2
The Goal
Find the run of consecutive numbers with the biggest sum, and return the sum. The run can't be empty, so even an all-negative array has an answer.
At each index, work out the best run that ends there. A negative prefix only drags later sums down, so sometimes you drop it and start again.
Find the strongest run
Pick consecutive numbers, at least one, with the largest sum.
Scan once, and at each number either extend or restart.
Extend or Restart
Let current be the best sum of a run ending just before num. A run ending at num either extends that one, for current + num, or starts fresh at num. Keep the larger, and track the best you've seen:
current = max(num, current + num)
best = max(best, current)
At the first 4, current is -2. Extending gives 2 and restarting gives 4, so restart.
Keep the previous run and add the new number.
current + num
Kadane's Algorithm
Each state needs only the one before it, so two variables replace the table: current for the best run ending here, and best for the best anywhere.
current = best = nums[0]
for num in nums[1:]:
current = max(num, current + num)
best = max(best, current)
return bestStart both from nums[0], not 0. That keeps the run non-empty.
| Approach | Time | Space | How |
|---|---|---|---|
| Brute force | O(n^2) | O(1) | Try every start and end |
| Full DP array | O(n) | O(n) | Best sum ending at each index |
| Kadane's algorithm | O(n) | O(1) | Keep only the last state |
Walkthrough
Run it on [-2, 1, -3, 4, -1, 2, 1, -5, 4].
current restarts at 1, then at 4. From the 4 it keeps extending: 3, 5, 6. That 6 is the best, from [4, -1, 2, 1].
The -5 drops current to 1 and the last 4 lifts it to 5, but best stays 6. The answer isn't always the final current.
Checkpoint · predict the next step
Step 4 of 10 on the stage: Index 3: extend to -2 + 4 = 2, or restart at 4. Restarting is at least as big, so current = 4, and best rises to 4.
current = [-2, 1, -2, 4, ·, ·, ·, ·, ·] · current 4 · best 4
Pitfalls
Starting best at 0 is the classic bug, because it quietly allows an empty run. For [-8, -3, -6] it returns 0, but the answer is -3.
Start from nums[0] instead: current = best = -8. At the -3, current = max(-3, -11) = -3, and best becomes -3.
A one-element array then needs no special case.
What should Kadane's algorithm return for [-8, -3, -6, -2]?
Complexity
Each number gets one addition and two comparisons: O(n) time. You keep current and best, so extra space is O(1).
Every number has to be read, so nothing is faster.
One scan, two variables
- Scan the arrayEach number once.dominantO(n)
- Extend or restartOne addition, one max.O(1)
- DP statecurrent and best.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
As fast as reading the input, in constant memory.
In short
Kadane's algorithm keeps the best subarray sum ending at the current index: current = max(num, current + num). Track the overall maximum as you go. Restarting whenever the running sum would drag you down is the whole trick.
Common mistake
Initializing the max to 0 — with all-negative inputs the answer is the least-negative element, not 0.