4.26.1 — Maximum Subarray

LeetCode 53 · Medium · ★ Blind 75

The problem

Return the largest sum of any contiguous subarray. The subarray must hold at least one element.

[-2,1,-3,4,-1,2,1,-5,4]   →  6     ([4,-1,2,1])
[-1]                      →  -1
[5,4,-1,7,8]              →  23

The pattern

This is Kadane's algorithm, and it rests on one observation:

A running sum that has gone negative is worse than starting fresh.

If the best subarray ending at the previous position had a negative total, then attaching it to the current element makes things worse. Dropping it and starting again at the current element is strictly better.

So walk once, carrying "the best sum ending here":

\text{best ending here} = \max\big(n,\ \ n + \text{best ending at the previous position}\big)

and keep the largest such value seen anywhere.

Why this is greedy and not DP. It is technically a one-line DP, but the choice at each step — extend or restart — can be decided immediately with no lookahead, and the decision is provably right. That is what makes greed safe here.

Why the "reset when negative" rule is safe

Worth being able to prove, because it is the follow-up.

Suppose the running sum up to position i−1 is negative, and the true best subarray starts somewhere at or before i−1 and ends at or after i. Then that subarray includes the negative stretch, and removing it gives a larger sum with the same endpoint. So the best subarray ending at i never includes a negative prefix. Discarding it loses nothing.

That is an exchange argument — take any supposedly optimal answer, show a modification that is at least as good, and conclude the greedy choice is safe. 4.25 builds the technique properly, and this is its cleanest instance.

The solution

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best_here = best_overall = nums[0]

        for n in nums[1:]:
            best_here = max(n, best_here + n)        # extend, or start fresh
            best_overall = max(best_overall, best_here)

        return best_overall

TypeScript

function maxSubArray(nums: number[]): number {
  let bestHere = nums[0], bestOverall = nums[0];

  for (let i = 1; i < nums.length; i++) {
    bestHere = Math.max(nums[i], bestHere + nums[i]);
    bestOverall = Math.max(bestOverall, bestHere);
  }

  return bestOverall;
}

Both variables start at nums[0], not at 0. This is the detail that decides whether the all-negative case works. For [-3, -1, -2] the answer is -1, and starting at 0 would wrongly return 0 — a subarray must be non-empty.

Two variables, and they mean different things. best_here is the best subarray ending at the current position; best_overall is the best seen anywhere. The best subarray may have ended long ago, so it must be recorded separately — the same "return one thing, record another" structure as 4.14.3 Diameter.

max(n, best_here + n) is the whole decision. Taking n alone means restarting; taking the sum means extending.

Trace

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

n	best_here + n	best_here	best_overall
−2	—	−2	−2
1	−1	1 (restart)	1
−3	−2	−2	1
4	2	4 (restart)	4
−1	3	3	4
2	5	5	5
1	6	6	6
−5	1	1	6
4	5	5	6

Answer 6, from [4,-1,2,1] ✓. Note the two restarts — each happened exactly when the running total had gone below the current element.

Complexity

O(n) time, O(1) space.

Returning the subarray itself

If asked for the indices rather than the sum, track where the current run started and record it whenever best_overall improves:

start = best_start = best_end = 0
for i in range(1, len(nums)):
    if best_here + nums[i] < nums[i]:
        best_here = nums[i]
        start = i                        # a restart begins here
    else:
        best_here += nums[i]
    if best_here > best_overall:
        best_overall = best_here
        best_start, best_end = start, i

The extra bookkeeping is small, and it is the natural follow-up.

The divide-and-conquer version

There is an O(n \log n) solution: split the array in half, and the answer is the best in the left half, the best in the right half, or the best crossing the middle — which is computed by extending outward from the centre in both directions.

Slower than Kadane's, and worth naming for one reason: it is the standard illustration of "the answer might straddle the split", and the same reasoning appears in segment trees.

Where this goes next

• Maximum Product Subarray — the multiplicative version, where Kadane's rule breaks because a negative can flip the worst into the best. 4.23.9. The contrast is the lesson: greed is safe for sums and not for products.
• Maximum Sum Circular Subarray — split into "does not wrap" (plain Kadane) and "wraps" (total minus the minimum subarray). The same circular-split idea as 4.23.4. Watch the all-negative case, where the wrapping branch would return an empty subarray.
• Best Time to Buy and Sell Stock — Kadane's on the daily price differences. 4.6.1.

What the interviewer will push on

"Why is it safe to restart when the running sum goes negative?" The exchange argument above. This is the question.

"What if every number is negative?" The answer is the largest single element, which is why the variables start at nums[0] rather than 0.

"Why two variables?" The best subarray may have ended earlier than the current position.

"Can you return the subarray?" Track the start index and record it on improvement.

"Can you do it in O(\log n)?" No — you must look at every element, so O(n) is a lower bound.

One thing to volunteer: note that Best Time to Buy and Sell Stock is this algorithm on differences. Connecting two problems that look unrelated is the strongest signal available.

Next: 4.26.2 Jump Game — where the greedy rule is even simpler and the proof is the interesting part.