LeetCode 53 – Maximum Subarray | Love Me Some Coding

Maximum Subarray is the smallest problem that is genuinely dynamic programming, and it is worth more preparation time than its length suggests. The solution is four lines. Almost everyone gets those four lines nearly right and fails on an input made entirely of negative numbers.

The problem

Given an integer array, find the contiguous subarray with the largest sum and return that sum. The subarray must be non-empty.

[-2,1,-3,4,-1,2,1,-5,4]  -> 6      the run [4,-1,2,1]
[1]                      -> 1
[5,4,-1,7,8]             -> 23     the whole array
[-1]                     -> -1
[-3,-1,-2]               -> -1     every choice is bad; pick the least bad one

That last line is the whole test. Read it twice.

Why brute force is not just slow

Every subarray is a start and an end, so there are O(n²) of them, and summing each one naively makes it O(n³). Carrying a running sum drops that to O(n²), which is already a hint: if maintaining one running sum saved a whole factor, maybe the right number of running sums is one.

The reframing

Do not ask "what is the best subarray?" — that question ranges over O(n²) candidates and gives you nothing to iterate on. Ask instead:

What is the best subarray ending exactly at index i?

That version has one answer per index, and each answer follows from the one before it. A subarray ending at i either starts at i, or it extends the best subarray ending at i - 1. There is no third option, because "contiguous" leaves nowhere else for it to begin.

endingHere[i] = max(nums[i], endingHere[i-1] + nums[i])
answer        = max over all i of endingHere[i]

And since endingHere[i] reads only endingHere[i-1], the table collapses to a single variable. That is Kadane's algorithm; you have just derived it rather than recalled it, which is what you want to be able to do out loud.

The intuition in one sentence: if the run so far has gone negative, it can only hurt whatever comes next, so drop it and start again.

The initialisation that fails the negative test

Starting best = 0 is the near-miss almost everyone writes. It silently encodes "the empty subarray is allowed, and it sums to 0", so [-3,-1,-2] returns 0 instead of -1. The problem said non-empty.

best = 0        -> [-3,-1,-2] returns 0    wrong
best = nums[0]  -> [-3,-1,-2] returns -1   right

Integer.MIN_VALUE also works, but seeding from nums[0] and starting the loop at index 1 is better: it states in code that the answer is some real element, and it makes the empty-array precondition impossible to overlook.

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int endingHere = nums[0];
        int best = nums[0];      // NOT 0 -- an all-negative array must return its largest element

        for (int i = 1; i < nums.length; i++) {
            // Start fresh at nums[i], or extend the best run that ended at i-1.
            endingHere = Math.max(nums[i], endingHere + nums[i]);
            best = Math.max(best, endingHere);
        }

        return best;
    }
}

Note that best and endingHere are different variables and returning the wrong one is a real failure mode. endingHere is the run in progress; best is the high-water mark. On [5,4,-1,7,8,-100] the run in progress ends at -77 and the answer is 23.

Python

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        ending_here = best = nums[0]

        for x in nums[1:]:
            ending_here = max(x, ending_here + x)
            best = max(best, ending_here)

        return best

float("-inf") is available in Python and works, but it invites returning a float from an integer problem. Seeding from nums[0] avoids the question.

The follow-up: where does the subarray start?

"Return the indices too" is the standard extension, and it is asked because it exposes whether the loop is understood or memorised. The change is that the choice inside Math.max becomes an explicit branch — extending keeps the current start, starting fresh moves it:

        int endingHere = nums[0], best = nums[0];
        int start = 0, bestStart = 0, bestEnd = 0;

        for (int i = 1; i < nums.length; i++) {
            if (endingHere + nums[i] < nums[i]) {
                endingHere = nums[i];        // starting fresh wins
                start = i;                   // ...so the run begins here
            } else {
                endingHere += nums[i];       // extending wins; start is unchanged
            }

            if (endingHere > best) {
                best = endingHere;
                bestStart = start;
                bestEnd = i;
            }
        }

Use > rather than >= on the best update unless you want the last of several equal-scoring runs. Either is defensible; being asked which one you chose and not knowing is not.

The divide-and-conquer answer

The problem statement often names it explicitly. Split the array in half; the best subarray lies entirely in the left half, entirely in the right half, or crosses the midpoint. The first two are recursive calls, and the crossing case is a linear scan outwards from the middle. That gives T(n) = 2T(n/2) + O(n), so O(n log n).

It is a good answer to a different question. Bring it up as the thing Kadane beats, and note when it earns its keep: the crossing-sum idea is what generalises to a segment tree, which is what you want when the array is being updated between queries.

Complexity

Approach	Time	Space
All subarrays	`O(n²)`	`O(1)`
Divide and conquer	`O(n log n)`	`O(log n)` stack
Kadane	`O(n)`	`O(1)`

The pattern

"Best thing ending at i, then take the max over i" is a template, not a one-off. Best Time to Buy and Sell Stock (121) is this algorithm on the array of day-to-day differences. Maximum Product Subarray (152) is the same recurrence carrying two values instead of one, because a large negative becomes a large positive when the next number is also negative. Maximum Sum Circular Subarray (918) runs Kadane twice — once for the maximum, once for the minimum, since the best wrapping run is the whole array minus the worst non-wrapping one.

What the interviewer is checking

That you reframe to "best subarray ending at i" rather than searching all subarrays.
best = nums[0], not 0 — the all-negative case is the whole point.
That best and endingHere stay distinct and you return the right one.
That you can state the recurrence before writing the loop.
The single-element array, which must return that element even when it is negative.
That you can extend it to report the indices without rewriting it.
That you know the O(n log n) divide-and-conquer exists and why you are not using it.