Kadane Maximum Subarray
The maximum subarray problem asks for the contiguous run of numbers with the greatest total sum. Kadane algorithm solves it in one linear pass, which is far better than checking every possible subarray.
The running idea
Scan left to right keeping a value called current that is the best sum ending exactly at the current position:
- At each element decide whether to extend the previous run by adding the element, or to restart the run at this element alone.
- Pick whichever is larger, then update a separate best value that tracks the highest sum seen anywhere.
The trick is that a negative running sum is never worth keeping, so you drop it and start fresh.
Handling negatives
If every number is negative the answer is the single largest number, so initialize best to the first element rather than zero to handle that case correctly.
Key idea
Carry the best sum ending here and restart whenever the running total turns negative.