Find the contiguous subarray with the largest sum, and return that sum.
DSA Animator › DSA Revision › Arrays › Maximum Subarray
Remember Kadane's rule: extend the run, or restart when the run is negative. Keep the best sum separately from the current run. The video solves Maximum Subarray (LeetCode 53, Medium) with the Kadane's Algorithm pattern from the Arrays topic, and you can replay every step in the interactive Maximum Subarray animation.
Find the contiguous subarray with the largest sum, and return that sum.
For minus 2, 1, minus 3, 4, minus 1, 2, 1, minus 5, 4, the best subarray is 4, minus 1, 2, 1. Its sum is 6.
Checking every subarray is O of n squared. And you cannot simply skip negatives, because the best run here contains a minus 1.
At each index, either extend the current run, or start a fresh run from here. If the running sum has gone negative, it only hurts what comes next, so drop it.
Minus 2: start at minus 2. At 1, the old sum is negative, so start fresh at 1. At minus 3, extend to minus 2. At 4, the old sum is negative again, so start fresh at 4. Minus 1, 2 and 1 extend the run to 3, then 5, then 6, the new best. Minus 5 drops it to 1, and 4 makes it 5, which does not beat 6. The answer is 6.
In code, cur is the larger of the number alone, or cur plus the number. Best tracks the largest cur seen. One pass, so it's O of n time and O of 1 space.
Remember Kadane's rule: extend the run, or restart when the run is negative. Keep the best sum separately from the current run.