A subarray is one unbroken run of the array. If every number is positive, the answer is the whole array, because each extra number raises the sum. Negative numbers make the problem hard, because the run must decide which numbers to keep.

Here dp[i] is the best sum of a subarray that ends exactly at index i. It is not the best sum in the first i numbers.

Look at a subarray that ends at x. It has only two forms. It is x alone, or it is a subarray that ends just before x, followed by x.

For the second form, the best choice is the best subarray that ends just before x. That value is curr. So the best sum ending at x is max(x, curr + x).

When curr is negative, curr + x is smaller than x, so the old run is dropped and a new run starts at x.

Every subarray ends at some index. The best subarray overall ends at one of them, and at that index curr already equals its sum.

So the largest curr over all indices is the answer. The variable best keeps that value.

This is why curr and best are two variables. curr can go down after a negative number. best never goes down.

Trace for nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The rows marked restart are the steps where curr drops the old run and starts again at x:

The answer is 6, from the run [4, -1, 2, 1].

Two steps restart the run. At 1, curr becomes 1 and not -2 + 1 = -1, because the old run was negative. At 4, curr becomes 4 and not -2 + 4 = 2, for the same reason. These restarts are where Kadane's rule does its work.

Linear DP keeps dp[i - 1] and dp[i - 2]. Here the formula needs only dp[i - 1], which is curr. The second variable best is not part of the recurrence. It records the maximum over all states.

This is a general pattern. When the answer is the best of all dp[i] and not the last dp[i], keep a running maximum next to the rolling value.

The start is curr = best = nums[0]. The subarray must hold at least one number, so an empty run at 0 is not allowed. An array of only negative numbers has a negative answer. For [-3, -1, -2], the answer is -1.

There are N states, and each does two max calls. The time is O(N) and the space is O(1).

The brute force checks every start and end, which is N * (N + 1) / 2 subarrays. For the nine numbers above, that is 45. The loop makes 8 passes.

Adding up each subarray from scratch costs O(N^3) in total. Keeping a running sum while the end moves right lowers it to O(N^2). Kadane's algorithm removes the loop over the start, so it is O(N).

To return the run and not only its sum, record start = i each time curr restarts at x. Record best_start and best_end each time best increases.

To find the best rectangle in a matrix of numbers, pick two rows r1 and r2. Add the numbers of each column from r1 to r2 into one array. The best run in that array is the best rectangle between those two rows, so run Kadane on it. There are O(rows^2) row pairs and each Kadane pass costs O(cols), so the total is O(rows^2 * cols).

For a circular array, as in Maximum Sum Circular Subarray (LC 918), the answer is the larger of two values. One is the normal Kadane result. The other is the total sum minus the smallest subarray sum. If every number is negative, return the normal result.