Kadane's Algorithm
Keep a running sum and drop it the moment carrying it forward hurts you.
0 of 3 problems solved
Kadane's Algorithm
Keep a running sum and drop it the moment carrying it forward hurts you.
- •Is this asking for the best contiguous subarray?
- •Can a negative running sum ever help later?
- •Should I compare extending vs starting fresh?
Maximum Subarray is the moment where brute force finally gets kicked out of the room. You do not need to test every possible subarray. Instead, carry a running sum as you move forward. If that running sum ever becomes negative, it stops being helpful. A negative backpack does not help you climb a hill; it only slows you down. So you drop it and start fresh from the current number.
If the running sum is negative, keeping it only makes the next subarray worse.
- 1Keep a current sum for the best subarray ending at this position.
- 2Keep a max sum for the best answer seen anywhere so far.
- 3For each number, decide whether to start fresh at this number or extend the previous subarray.
- 4Update the global maximum after each step.
Resetting to zero blindly can break cases where every number is negative. Compare against the current number itself, not just zero.
Running Sum of 1d Array
Each position is prefix[i] = prefix[i-1] + nums[i]. One forward pass builds the entire output array.
Maximum Sum of 3 Non-Overlapping Subarrays
Pre-compute the best window ending at or before each index and the best window starting at or after each index. Try every middle window and combine the three.