The maximum subarray
Kadane's algorithm finds the contiguous subarray with the largest total in a single pass. The insight is to track, at each position, the best sum of a subarray that ends right here, then take the maximum of those running bests.
The running decision
For each new element you face one choice: extend the previous best ending sum, or start fresh from the current element alone.
- Extend if the previous running sum is positive and helps.
- Restart at the current element if the previous running sum is negative and only drags you down.
Concretely, the best sum ending here is the current element plus the previous running sum, but never less than the current element by itself. You also keep a separate overall best that you update after each step.
Why a negative prefix resets
If the running sum ever drops below zero, carrying it forward can only reduce any future subarray, so discarding it and restarting is always at least as good. That single observation is what makes the one pass solution correct.
Key idea
Kadane keeps a best ending here running sum, restarting whenever the carried sum turns negative, and tracks the overall maximum, finding the largest contiguous total in one linear pass.