Part 2 · Problems · Simple DP
Maximum Subarray
#53 · Medium · LeetCode
Return the largest sum of a contiguous, non-empty subarray.
[-2,1,-3,4,-1,2,1,-5,4] -> 6 ([4,-1,2,1]) [-3,-1,-2] -> -1
Ask before coding
- All negatives possible?
- Non-empty?
Hint
At each index: is it better to extend the previous run or start over here?
Approach
Kadane: cur = max(num, cur + num). best = max(best, cur).
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function maxSubArray(nums) {
// Kadane: either extend the current run or start fresh here
let cur = nums[0],
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;
}Traps
- Starting best at 0 fails when every number is negative. Start at nums[0].
Say out loud: A negative running sum only hurts, so drop it and start fresh. One pass.