Maximum Subarray
Problem
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]6def max_subarray(nums):
cur = best = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return bestfunction maxSubarray(nums) {
let cur = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}class Solution {
public int maxSubarray(int[] nums) {
int cur = nums[0];
int best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}
}int maxSubarray(vector<int>& nums) {
int cur = nums[0];
int best = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
cur = max(nums[i], cur + nums[i]);
best = max(best, cur);
}
return best;
}Explanation
This is the famous Kadane's algorithm. The key question at each position is simple: should I keep extending my current run of numbers, or is the run dragging me down so much that I'm better off starting fresh from here?
We keep cur, the best sum of a subarray that ends at the current spot. At each number x we choose cur = max(x, cur + x). If cur + x is worse than just x alone, our past sum was negative baggage, so we drop it and restart at x.
Separately, best remembers the largest cur we've ever seen, so the answer survives even after cur later dips.
Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]. When we reach 4, the prior sum was negative, so we restart. Then 4, -1, 2, 1 builds cur up to 6.
Nothing afterward beats it, so best = 6. Because each step is one comparison, the whole thing runs in a single pass.