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.

Restating the Problem: You are given an array of integers that can contain both positive and negative numbers. Your task is to find a contiguous sequence (a slice of the array with no gaps) that adds up to the highest possible value.

• Constraints to note: The array length can be up to 10^5, meaning an O(N^2) solution will time out. The values range from -10^4 to 10^4.
• Edge cases: The array might be entirely negative. Since a subarray must contain at least one element, you cannot return 0 (an empty subarray) in this case; you must pick the single least-negative element.

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

Brute Force Approach

The naive approach is to check every possible subarray. You would use a nested loop: the outer loop picks a starting index i, and the inner loop picks an ending index j. For each pair (i, j), you compute the sum and keep track of the maximum. This takes O(n^2) time (or even O(n^3) if you recalculate the sum from scratch each time). With n = 10^5, n^2 = 10^{10} operations, which is way too slow and will result in a Time Limit Exceeded (TLE). The brute force wastes time by repeatedly calculating sums of overlapping subarrays without using previous results. We need a way to build on previous work.

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.

An Analogy: Imagine you are walking down a street collecting money, but some houses charge you a fee (negative numbers). If at any point the total fees you've paid exceed the money you've collected (your running sum goes negative), you would be better off just emptying your pockets and starting fresh from the next house. A negative balance only drags down any future gains.

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;
}

Code Walkthrough:

• Initialization: We set both best_here and best_overall to the first element. best_here tracks the maximum sum of a subarray that ends exactly at the current element. best_overall tracks the highest sum we've seen globally.
• Iteration: We loop through the array starting from the second element (index 1).
• The Core Decision (max(n, best_here + n)): At each step, we decide whether to add the current element n to the existing subarray (best_here + n), or to abandon the existing subarray and start a new one beginning with n itself. We start fresh only if best_here had dropped below zero.
• Updating the Global Maximum: After resolving best_here for the current index, we check if it beats our best_overall record and update it if so.
• Return: Finally, we return best_overall.

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.

• Time Complexity: O(n). We iterate through the array of n elements exactly once. At each step, we perform a constant amount of work (just a couple of addition and max operations). Thus, the total time scales linearly with the input size.
• Space Complexity: O(1). We only maintain two integer variables (best_here and best_overall), regardless of how large the input array is. We do not allocate any additional arrays or data structures, meaning memory usage is constant.

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.