Given an integer array (may contain negatives), find the contiguous subarray with the largest sum and return that sum. e.g. [-2,1,-3,4,-1,2,1,-5,4] → 6 (from [4,-1,2,1]).
Recognising that a running sum should be reset the moment it stops helping — the core Kadane insight.
At each index you make one decision: extend the previous best-ending-here subarray, or start fresh at the current element. Formally `cur = Math.max(x, cur + x)` — if the running sum has gone so negative that x alone is bigger, throw it away and restart. Track a separate `best` for the global maximum, because the best window may have ended before the array does. The trap is initialising `best` to 0: with an all-negative array like [-3,-1,-2] the answer is -1, not 0, so seed both `cur` and `best` with the first element (or -Infinity) and iterate from index 1. This is a 1-D DP collapsed to O(1) space — the 'DP where each state depends only on the previous state' family, the same shape as house-robber and best-time-to-buy-sell. To also recover the indices, remember where `cur` reset.
Best contiguous run (max sum / max product) in one pass → carry a running value, reset it when it stops helping.
Time O(n) · Space O(1)