#53
Maximum Subarray
Medium Kadane
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the contiguous non-empty subarray with the largest sum and return the sum.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the contiguous piece with the biggest sum.
Why this works: a running sum that has gone negative only drags down whatever comes next, so start over from the current number.
Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
cur: -2, 1, -2, 4, 3, 5, 6, 1, 5best = 6 → [4, -1, 2, 1]
✦Hints open one at a time
At each index decide: extend the previous subarray, or start fresh here?
Start fresh when the running sum would be smaller than the element alone.
↗Approach
Kadane's algorithm: cur = max(nums[i], cur + nums[i]); best = max(best, cur). A negative running sum can only hurt what comes next, so drop it.
</>Solution (Java)
class Solution {
public int maxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]); // extend or restart
best = Math.max(best, cur);
}
return best;
}
}!Common mistake
Starting best at 0 — if every number is negative, the answer is the largest negative, not 0.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon