Maximum Subarray
MediumGreedy
Given an array of integers nums, find the non-empty run of neighbouring values with the largest sum, and return that sum.
Examples
Input: nums = [3, -4, 5, -1, 2, -6, 1] Output: 6
5 + (-1) + 2 = 6.
Input: nums = [-7, -2, -9] Output: -2
The run cannot be empty, so the best is the single value -2.
Constraints
1 ≤ nums.length ≤ 10⁵-10⁴ ≤ nums[i] ≤ 10⁴
Stuck?
Hint 1
Walk left to right. A run ending here either extends the best run ending one step earlier or starts fresh at this value: whichever is bigger.
Hint 2
Start fresh exactly when the running sum has gone below zero. Keep the best sum seen, and start it at the first value, not at 0, since every value may be negative.
The idea
The best run ending at a value either extends the best run ending one step earlier or starts fresh at that value. Extending helps only when that earlier run sums to more than zero, so a negative running sum is dropped. The answer is the largest of these runs, wherever it ends.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
current is the best sum of a run ending at the current value, and best the best sum seen anywhere. Both start at the first value, not at 0: the run cannot be empty, and when every value is negative the answer is negative.
function maxSubArray(nums) { let current = nums[0]; let best = nums[0]; for (let i = 1; i < nums.length; i++) { current = Math.max(nums[i], current + nums[i]); best = Math.max(best, current); } return best;}The trap
Starting current and best at 0 and resetting current to 0 whenever it drops below zero works whenever some value is positive, so it passes most arrays. Both lines treat the empty run, with sum 0, as an answer. When every value is negative the best real run is negative, but this version never goes below 0 and returns 0.
function maxSubArray(nums) { let current = 0; let best = 0; // wrong when every value is negative for (const n of nums) { current = Math.max(0, current + n); best = Math.max(best, current); } return best;}