Maximum Subarray
Maximum Subarray is LeetCode 53 (Medium). Given an integer array nums, find the contiguous subarray with maximum sum (it must contain at least one element), and return that sum.
- A subarray is a run of neighbouring elements; you cannot skip elements.
- The array may contain negative numbers, and may be all negative. The subarray must still contain at least one element.
- Follow-up: after the O(n) solution, try divide and conquer.
With up to 10⁵ elements, checking every subarray (about 5 · 10⁹ pairs) is too slow; the target is one pass.
- 1 <= nums.length <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
Intuition
The maximum subarray problem asks for the best contiguous run. Kadane's algorithm solves it in one pass by asking a smaller question at each index i:
> What is the best sum of a subarray that ends exactly at i?
That subarray is either nums[i] on its own, or the best one ending at i - 1 with nums[i] added. The answer is the largest of these over all indices. It is dynamic programming with one number of state, so it runs in O(n) time and O(1) space.
"Largest (or smallest) sum of a contiguous subarray" is Kadane's algorithm. The same restart-or-extend idea gives Maximum Product Subarray (track both a max and a min), the circular version (LeetCode 918: total minus the minimum subarray), and best time to buy and sell stock (Kadane on the day-to-day price differences).
Approach
Before reading on: for [-2, 1, -3, 4, -1, 2, 1, -5, 4], write the best sum of a subarray that ends at each index. When does it pay to throw away everything before the current element? What should the answer be for [-3, -1, -2]?
Two ways to solve it
One pass keeps cur, the best run ending here, and restarts it whenever the run so far is negative.
- Work: each element touched once.
- Memory: two variables.
- Code: a five-line loop.
The answer interviewers expect for LeetCode 53, in any language.
Split at the middle: the best run lies in the left half, the right half, or crosses the middle.
- Work: a linear scan per level, log n levels.
- Memory: the recursion stack.
- Code: a helper plus two scans.
The follow-up LeetCode asks for.
Kadane's algorithm is faster and needs no recursion, so the steps, code and live demo below follow it. Divide and conquer answers the problem's follow-up; its code comes after the demo.
Start with the first element
cur = best = nums[0]: the only subarray ending at index 0 is that element alone. Starting best at 0 would be wrong when every number is negative.
Restart or extend at each element
For each next x:
cur < 0: start a new run,cur = x;- otherwise: extend the run,
cur += x.
A negative running sum can only drag the next element down, so dropping it never loses the answer.
Track the best run end
best = max(best, cur) after every element, since the optimal subarray can end at any index.
Return best
After one pass, best is the maximum subarray sum. Each index was considered as an end exactly once with its best start.
Maximum Subarray solution in Python | C++ | Java
[-2], so cur = best = -2. Starting from 0 instead would invent an empty subarray, which is wrong when every number is negative.cur reached is 6, the sum of [4, -1, 2, 1]. Every subarray ends somewhere, and at each end cur held the best sum for that end, so nothing was missed.[-3], so cur = best = -3. Starting from 0 instead would invent an empty subarray, which is wrong when every number is negative.cur reached is -1, the sum of [-1]. Every subarray ends somewhere, and at each end cur held the best sum for that end, so nothing was missed.[5], so cur = best = 5. Starting from 0 instead would invent an empty subarray, which is wrong when every number is negative.cur reached is 23, the sum of [5, 4, -1, 7, 8]. Every subarray ends somewhere, and at each end cur held the best sum for that end, so nothing was missed.Divide and conquer
best(lo, hi) returns the maximum subarray sum inside nums[lo..hi]. It recurses on both halves, and finds the best run crossing the middle by growing one run leftwards from mid and one rightwards from mid + 1.
Common pitfalls
Starting best at 0
best = 0 cur = 0
cur = best = nums[0]
For [-3, -1, -2] nothing ever beats 0, so the answer comes out as 0, the sum of an empty subarray, which is not allowed. The correct answer is -1.
Restarting whenever the next element is negative
if x < 0:
cur = 0if cur < 0:
cur = x
else:
cur += xWhat matters is whether the run so far is negative, not the new element. In [5, 4, -1, 7, 8] restarting at -1 loses the 9 before it and returns 15 instead of 23.
Updating best only when restarting
if cur < 0:
best = max(best, cur)
cur = xbest = max(best, cur) # after every element
The best run may never be followed by a restart, as in [1, 2, 3], where the answer 6 is only reached at the last element.
Complexity
Maximum Subarray FAQ
How does Kadane's algorithm work?
- State:
cur= best sum of a subarray ending at the current index;best= best sum seen anywhere. - Start:
cur = best = nums[0]. - Each next x: if
cur < 0, restart withcur = x; otherwisecur += x. Thenbest = max(best, cur). - Answer:
best. - Why: a negative run can only lower whatever comes after it, so it is dropped.
- Complexity: O(n) time, O(1) space.
How do you return the maximum subarray itself, not just its sum?
Track where the current run started: set start = i on every restart. Whenever best improves, save (start, i). At the end, the saved pair gives the subarray.
Is maximum subarray dynamic programming?
Yes. dp[i] = max(nums[i], dp[i-1] + nums[i]) is the best sum ending at index i, and the answer is max(dp). Kadane's algorithm is this recurrence with the table reduced to one variable, since dp[i] only needs dp[i-1].