Maximum Subarray
You're given an integer array nums, which may contain negative numbers. Find the contiguous subarray, at least one element long, with the largest sum, and return that sum (not the subarray itself). If every number is negative, the answer is the largest single element.
Examples
nums = [-2,1,-3,4,-1,2,1,-5,4] returns 6
The run [4,-1,2,1] at indices 3 to 6 adds to 6. Keeping the -1 is worth it because it connects 4 to 2 and 1, and no other run does better.
nums = [1] returns 1
The only subarray is [1] itself.
nums = [5,4,-1,7,8] returns 23
The whole array is best: the -1 costs less than the 7 and 8 it connects to, so all five values add to 23.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Hints
Suppose you know the best sum of a run that ends at index i - 1. How does that help with the best run ending at index i?
Dynamic programming over the best sum ending at each index, also known as Kadane's algorithm.
Start cur and best at nums[0]. For each later value n, set cur = max(n, cur + n), then best = max(best, cur). Return best.
Drill This: Your Approach First
Approach
Let cur be the best sum of a subarray that ends exactly at the current index. At each new value n, either extend the previous run (cur + n) or start fresh at n, whichever is larger: a run with a negative total only drags down whatever follows it. The answer is the largest cur seen at any index. This is Kadane's algorithm, one pass with two variables.
Time
O(n)
Space
O(1)
Pitfall
Solutions
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]);
best = Math.max(best, cur);
}
return best;
}
}class Solution:
def maxSubArray(self, nums) -> int:
cur = best = nums[0]
for n in nums[1:]:
cur = max(n, cur + n)
best = max(best, cur)
return best