Kadane's Maximum Subarray Explained: Tracing [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Imagine you are handed the sequence $\text{nums}=[-2,1,-3,4,-1,2,1,-5,4]$ and asked to find the contiguous subarray that yields the largest possible sum. If you approach this with a naive brute-force mindset, you might think of checking every single starting and ending index combination. With $N$ elements, there are $\frac{N(N+1)}{2}$ possible subarrays, which explodes quickly as $N$ grows. For our specific array of 9 elements, that means evaluating 45 distinct slices. If your array scales to 100,000 elements, brute force requires billions of operations, dragging performance down to a crawl. Worse yet, what happens when you encounter an array like $\text{nums}=[-1,-2,-3]$ where every number is negative? A naive approach that defaults to an empty sum of 0 will completely fail the constraint that at least one element must be selected. Kadane's maximum subarray explained starts right here: how do we inspect every relevant contiguous slice in a single pass without recomputing sums from scratch?

When examining our running target array $\text{nums}=[-2,1,-3,4,-1,2,1,-5,4]$, a naive $O(n^2)$ slice check forces us to recompute overlapping windows repeatedly. Kadane's algorithm replaces this redundancy with a dynamic programming mindset, asking a single local question at each index $i$: do I extend the previous running subarray, or do I drop it and start a fresh subarray right here?

Let us execute our model on the primary array from our locked example: $\text{nums}=[-2,1,-3,4,-1,2,1,-5,4]$. We track two variables at every index $i$: $\text{currentSum}$, which decides whether to extend the previous subarray or start fresh at $\text{nums}[i]$, and $\text{maxSum}$, which records the global record seen so far.

Now that you have seen how Kadane's algorithm traces through the mixed sequence $[-2,1,-3,4,-1,2,1,-5,4]$ to find a maximum sum of 6, it is time to test your grasp of the update rules on the second half of our locked example: the all-negative sequence $\text{nums}=[-1,-2,-3]$.

The pattern we uncovered while tracking $[-2,1,-3,4,-1,2,1,-5,4]$ and $[-1,-2,-3]$ is not just for finding contiguous sums in static arrays. Whenever you need to find a maximum contiguous window where local decisions either anchor a new start or extend an existing run, this exact dynamic programming skeleton applies. For instance, consider finding the maximum profit from daily price changes instead of raw numbers, or processing an infinite real-time telemetry stream where memory is bounded and you can only keep running counters. The core insight—that a negative running accumulator should be dropped because it hurts any future contribution—translates directly to any domain dealing with local drag versus explosive upside.

def max_subarray_profit_stream(price_changes):
    # TODO: Apply Kadane's tracking to price changes
    pass