Kadane's Algorithm

Track current sum. At each position:

• Add the current element to current sum.
• If current sum < $0$, reset to $0$ (start fresh from next element).
• Update max sum seen. The core idea: a negative prefix never helps. If the sum so far is negative, throw it away and start fresh. Time: $O(n)$. Space: $O(1)$. Common bug: resetting before checking max, which loses single positive elements surrounded by negatives.