Maximum Subarray Sum

One number about the past

A food truck logs its daily profit, in hundreds of dollars, for nine days:

day:      0   1   2   3   4   5   6   7   8
profit:  -2   1  -3   4  -1   2   1  -5   4
                      └───────────┘
               days 3–6: 4 − 1 + 2 + 1 = 6

The owner wants to brag about the best run of consecutive days. Days 3 to 6 made 6, and no other run beats it. Finding that run is LeetCode 53: Maximum Subarray.

The obvious plan tries every start and every end. With n = 100,000 days, LeetCode's limit, there are n(n+1)/2 = 5,000,050,000 runs. Even if you grow each run one number at a time instead of re-adding it, recent CPython versions spend roughly 40 to 100 nanoseconds per step, so the answer takes about three to eight minutes. Re-adding every run from scratch would take about 1.7 × 10¹⁴ additions.

The fix is to keep exactly one number about the past: the best sum of a run that ends right here. Each new day either extends that run or starts a new one, and one comparison decides which. That is Kadane's algorithm: one pass, O(n) time, O(1) extra space. The rest of this lesson changes what the "one number" has to be as the problem changes.

This lesson builds on Foundation: Arrays & Strings, especially its running summary (the hindsight trader), the difference between a subarray and a subsequence, and prefix sums. It sits under Sliding Window Patterns, and one section below explains why Kadane's algorithm is not a sliding window, even though it looks like one.

Before any code: read the contract

LeetCode 53 asks for the largest sum of a non-empty, contiguous subarray, and returns only the sum. Constraints: 1 ≤ n ≤ 10⁵ and −10⁴ ≤ nums[i] ≤ 10⁴.

Three parts of that sentence carry the weight:

• Contiguous. If you could skip elements, you would just add up the positives: 1 + 4 + 2 + 1 + 4 = 12 for the food truck. Contiguity is what makes the problem hard.
• Non-empty. On [-3, -1, -4, -2] the answer is −1, the single least-bad day. Some versions allow the empty subarray, worth 0. Jon Bentley's 1984 column that made this problem famous allowed it, and so does the stock problem's "don't trade". Then the answer can never be negative. Check which version you are solving, because it decides how you initialize.
• Only the sum. Returning where the run starts and ends is a different contract (Move 3).

What about an empty list? LeetCode never sends one. Most functions in this lesson read nums[0], so they raise IndexError on []. The two that allow the empty run, max_profit and max_absolute_sum, return 0, which is a legal answer for their problems. If your caller might pass an empty list, choose the behaviour on purpose: raise ValueError, or return None. Don't return 0. Zero is also a real answer, for [0] or [-3, 0], so the caller couldn't tell "no data" from "the best run is worth 0".

Move 1: Carry the best sum ending here

Smell: for each position, the slow code loops back over every possible start.

The slow version and what it repeats

def max_subarray_slow(nums):
    best = nums[0]
    for i in range(len(nums)):          # start
        total = 0
        for j in range(i, len(nums)):   # end
            total += nums[j]            # total = sum of nums[i..j]
            best = max(best, total)
    return best

This is already one step smarter than the most naive version: it grows total by one number at a time instead of re-adding nums[i..j] in a third loop, which would cost O(n³). It still visits all n(n+1)/2 (start, end) pairs, so it is O(n²) time and O(1) extra space. Keep it anyway: it is the reference every fast version below was tested against.

Now group the same runs by where they end. For every end j, the slow code is really asking: what is the best sum of a run that ends exactly at j? It answers that from scratch every time. But a run that ends at j is always one of two things:

• just [nums[j]], or
• a run that ends at j − 1, with nums[j] attached.

Predict first: in [3, -4, 5], should the best run ending at the 5 include the 3 and the −4?

Extend or start fresh

That observation is the whole algorithm. Carry one number, ending_here, and update it with one comparison:

def max_subarray(nums):
    ending_here = nums[0]    # best sum of a run that ends at the current index
    best = nums[0]           # best sum of any run seen so far
    for i in range(1, len(nums)):
        x = nums[i]
        ending_here = max(x, ending_here + x)   # start fresh at x, or extend
        best = max(best, ending_here)
    return best

Here is a trace on the food-truck data. The "extend" column is the previous ending_here plus x:

There are two restarts, at index 1 and at index 3, because the run ending just before each of them was −2. From index 3 on, ending_here never goes negative, so the run keeps extending and best locks in at 6 at index 6. Index 7 still extends, since 6 − 5 = 1 beats −5 alone, but it doesn't improve best. The function returns 6 after one pass: O(n) time and O(1) extra space, where n = len(nums), as everywhere in this lesson.

Why it works

The invariant: after processing index i, ending_here is the largest sum of a run that ends exactly at i, and best is the largest sum of any run inside nums[0..i].

It holds at index 0. At index i, every run that ends at i is either [x] alone or a run ending at i − 1 with x attached. The best run of the second kind uses the best run ending at i − 1, which is exactly ending_here. So max(x, ending_here + x) is the best run ending at i. The best run overall ends somewhere, and best looked at every possible ending.

🧠 Dynamic programming with one state. The subproblem is "best sum of a run ending at i". It depends only on the subproblem at i − 1, so a table of n answers collapses into one variable. The final answer is not the last state: it is the best of all of them. Return ending_here instead of best and you get the best run that ends at the last index, which is 1 instead of 5 for [5, -9, 1]. Dynamic Programming Mastery builds this way of thinking out properly.

It is the same move as the hindsight trader in the Foundation lesson, with a different notebook. The trader carried "cheapest earlier price". Here you carry "best run ending here".

A little history. Ulf Grenander posed the problem in 1977 while looking for patterns in digitized pictures. His one-dimensional algorithm was quadratic. Michael Shamos found an O(n log n) divide-and-conquer algorithm overnight, and a few days later he described the problem at a Carnegie Mellon seminar. Jay Kadane, a statistician in the audience, designed the linear scan within a minute. Bentley told the story in his Programming Pearls column in 1984, along with a race. He ran the cubic algorithm in tuned FORTRAN on a Cray-1 supercomputer and the linear one in BASIC on a Radio Shack TRS-80 home computer. The Cray won on small inputs, and the two broke even around n = 2,500. At n = 100,000 his timing formulas give the Cray 35 days and the TRS-80 32 minutes.

The same algorithm with a reset to zero

Many books write Kadane's algorithm like this:

def max_subarray_reset(nums):
    ending_here = 0
    best = nums[0]
    for x in nums:
        ending_here += x
        best = max(best, ending_here)   # record first...
        if ending_here < 0:
            ending_here = 0             # ...then drop a run that went negative
    return best

It is the same algorithm. max(x, e + x) equals x + max(e, 0): keep the previous run only if it is not negative. Zeroing a negative ending_here before the next x is added computes exactly that. Resetting to 0 is not a bug.

The order can be a bug. Move best = max(best, ending_here) below the reset, and a negative run gets zeroed before it is recorded. On [-5] the function then returns 0, which is the sum of the empty run. If you want the empty run, start with best = 0. That gives Bentley's version, whose answer is never negative.

Traps

⚠️ best = 0. On [-3, -1, -4, -2] it returns 0, an empty run the contract forbids. Start best at nums[0], or at float('-inf').

⚠️ Skipping index 0 without accounting for it. The loop starts at 1 because both variables were initialized from nums[0]. If you start the loop at 1 but set ending_here = 0, index 0 can never join a longer run, and [2, 3] returns 3 instead of 5. This bug hits an all-positive input, not an all-negative one.

⚠️ for x in nums[1:]. It reads nicely, but the slice copies n − 1 elements, so extra space becomes O(n). On a list of a million numbers, peak extra memory measured about 8 MB for the slice loop and a few hundred bytes at most for the index loop. Use range(1, len(nums)) or itertools.islice(nums, 1, None).

⚠️ Other languages. Python integers never overflow. In Java or C++, 32-bit sums are safe for LeetCode 53, because every sum stays within 10⁵ × 10⁴ = 10⁹ < 2,147,483,647. But initializing ending_here to Integer.MIN_VALUE instead of nums[0] makes ending_here + x overflow whenever the first element is negative: MIN_VALUE + x wraps around to a huge positive number, and max keeps it.

Your turn: the worst run

Write min_subarray(nums), the smallest sum of a non-empty contiguous run. Predict its answer for [3, -4, 2, -3, -1, 7, -5]. Then find an input that breaks it if you start best at 0.

def min_subarray(nums):
    ending_here = best = nums[0]
    for i in range(1, len(nums)):
        x = nums[i]
        ending_here = min(x, ending_here + x)
        best = min(best, ending_here)
    return best

Move 2: The hindsight trader, again

Smell: the problem is really about the difference between two running totals.

Predict first: the running totals of [5, -10, 3, 4] are 5, −5, −2, 2. The highest one is 5, right after the first element. Is the answer 5?

Prefix sums turn runs into differences

Recall prefix sums from the Foundation lesson: prefix[0] = 0, and prefix[k] is the sum of the first k elements. The run from i to j sums to prefix[j + 1] − prefix[i]. So:

best run ending at j = prefix[j + 1] − (the lowest prefix[i] with i ≤ j)

That is the hindsight trader again. The prefix sums play the prices: buy at the lowest earlier reading and sell at today's. "Buy strictly before you sell" is what keeps the run non-empty.

def max_subarray_prefix(nums):
    running = 0      # prefix sum through the current element
    lowest = 0       # lowest earlier prefix sum; 0 is the empty prefix
    best = nums[0]
    for x in nums:
        running += x
        best = max(best, running - lowest)   # sell at today's reading...
        lowest = min(lowest, running)        # ...then today may become a buy
    return best

Now look at the running − lowest column: −2, 1, −2, 4, 3, 5, 6, 1, 5. It matches the ending_here column from Move 1, number for number. The two functions are one algorithm told two ways. Kadane "starts fresh" exactly when the running total has just hit a new low. The running total drops to −4 at index 2, which is the lowest point so far, so the best next run starts right after it, at index 3.

The order of the two lines inside the loop matters for the same reason it did for the trader. Update lowest first, and today's reading can be both the buy and the sell. That is the empty run again: [-3, -1] returns 0.

Your turn: LeetCode 121 in disguise

LeetCode 121: Best Time to Buy and Sell Stock is the Foundation lesson's hindsight trader. Turn it into a maximum-subarray problem. From prices [7, 1, 5, 3, 6, 4], build the list of day-to-day changes and run Kadane on it. Why is the result the best profit, and why must your version allow the empty run?

def max_profit(prices):
    best = ending_here = 0          # the empty run: "don't trade" is worth 0
    for i in range(1, len(prices)):
        change = prices[i] - prices[i - 1]
        ending_here = max(0, ending_here + change)
        best = max(best, ending_here)
    return best

The same trick works whenever a problem compares two arrays position by position or measures gains against a baseline: build the derived array of changes, differences or gains, then run Kadane on it.

Where prefix sums go further

Kadane keeps only the lowest earlier reading, which is enough for "largest". It is not enough for "how many runs sum to exactly k". For that you need to know which specific readings occurred, so you store the prefix sums in a hash map and look up running − k at each step. That is LeetCode 560: Subarray Sum Equals K, taught in Hash Maps & Sets.

Why this is not a sliding window

Kadane's current run has a left end and a right end, and the right end moves one step at a time. It looks like a sliding window, but it isn't one, and the difference matters when you choose a technique.

A variable sliding window, from Sliding Window Patterns, grows on the right and shrinks on the left one step at a time. A rule such as "shrink while the sum is at least the target" drives it. That rule works only when every step moves the quantity in a predictable direction. With all-positive numbers, growing always raises the sum and shrinking always lowers it.

Negative numbers break that. Adding a −1 lowers the sum now, but it may be the price of reaching a later +3. Dropping the leftmost element can raise the sum or lower it. No local rule tells you when to shrink by one.

Predict first: a friend says, "a negative number only lowers a sum, so the best run never contains one." What does that rule give on [4, -1, 2, 1]?

So how does Kadane get away with it? Its left edge never slides. It jumps, and only after the whole run has gone negative. In between, a stronger fact holds: every proper prefix of the current run has a sum of at least 0. If one of them had gone negative, the run would already have restarted right after it. So trimming from the left can never raise the sum, and the left edge never needs to move by one. That fact comes from the extend-or-restart recurrence, not from a window rule.

Windows do fit some neighbouring problems:

• Fixed length. "Largest sum of exactly k consecutive elements" (LeetCode 643: Maximum Average Subarray I) is a fixed window: add the element that enters, subtract the one that leaves. Negatives are fine, because the length decides when to drop, not the sum. Kadane is wrong here: it ignores the length.
• All positive, with a threshold. "Shortest run with sum at least target" on positive numbers (LeetCode 209: Minimum Size Subarray Sum) is a variable window and runs in O(n). Allow negative numbers and its shrink rule breaks.

Move 3: Say where, not just how much

Smell: the contract asks for the run itself, or for its start and end.

A common interview follow-up is "now return the indices". That takes one extra idea: the start of the current run is only a candidate. It becomes the answer's start only when the current run beats best.

Predict first: in [5, -9, 4, 3], Kadane restarts at index 2. Should the reported start become 2 at that moment?

def max_subarray_span(nums):
    ending_here = best = nums[0]
    start = best_lo = best_hi = 0     # start: where the current run began
    for i in range(1, len(nums)):
        x = nums[i]
        if ending_here < 0:           # the run so far only hurts: start fresh at i
            ending_here = x
            start = i
        else:
            ending_here += x
        if ending_here > best:        # commit the candidate only on a new best
            best = ending_here
            best_lo, best_hi = start, i
    return best, best_lo, best_hi

if ending_here < 0 makes the same choice as max(x, ending_here + x). Here is the trace on the food-truck data:

It returns (6, 3, 6), and nums[3:7] is [4, -1, 2, 1]. Commits happen at indices 1, 3, 5 and 6. Index 1 counts too, because [1] beat the starting value −2. It is still O(n) time and O(1) extra space.

Ties: the sum is unique, the span isn't

In [2, -2, 2], the runs [2] at 0..0, [2] at 2..2 and [2, -2, 2] at 0..2 all sum to 2. The function returns (2, 0, 0): > commits only on a strict improvement, and ending_here == 0 extends rather than restarts. When a problem says which span to report (shortest, earliest, longest), treat the tie rules as part of the contract and test ties on purpose.

Your turn: change > to >=. What does the function now return for [-3, -1, -2], [2, -2, 2] and [1, -1, 1, -3, 1]?

Move 4: Around the corner

Smell: the array is a ring, so the element after the last one is the first.

LeetCode 918: Maximum Sum Circular Subarray asks for the largest sum of a non-empty run on a circular array, using each element at most once. Constraints: 1 ≤ n ≤ 3 × 10⁴, and each value is between −3 × 10⁴ and 3 × 10⁴.

Predict first: on the ring [5, -3, 5], what is the best run?

Two shapes of run

A run on a ring either stays inside the array or wraps past the end:

index:     0   1   2   3   4   5   6
no wrap:   .   .   #   #   #   .   .     one run inside the array
wrap:      #   #   .   .   .   #   #     a prefix plus a suffix
                   └───────┘      skipped: one middle run

A wrapping run keeps both ends and skips one contiguous middle. Its sum is total − (sum of the skipped middle), which is largest when the skipped middle is the smallest run. You wrote that function in Move 1: min_subarray. For [5, -3, 5], the total is 7 and the smallest run is −3, so the wrap is worth 7 − (−3) = 10.

The trap: the empty run sneaks back in

If every element is negative, the smallest run is the whole array. Then total − smallest = 0, and the "wrap" keeps nothing: it is the empty run. On [-3, -2, -3] the total is −8 and the smallest run is −8, so the wrap is worth 0, and max(-2, 0) answers 0 instead of −2. This is Move 1's best = 0 bug in disguise.

The guard: if plain Kadane's answer is negative, every element is negative, because any element ≥ 0 would form a run worth ≥ 0. In that case return plain Kadane's answer directly.

def max_circular(nums):
    total = best_max = best_min = max_here = min_here = nums[0]
    for i in range(1, len(nums)):
        x = nums[i]
        max_here = max(x, max_here + x)     # Kadane for the largest run
        min_here = min(x, min_here + x)     # Kadane for the smallest run
        best_max = max(best_max, max_here)
        best_min = min(best_min, min_here)
        total += x
    if best_max < 0:                         # all negative: a wrap would keep nothing
        return best_max
    return max(best_max, total - best_min)

It makes one pass: O(n) time, O(1) extra space.

Why the guard is enough. When best_max ≥ 0, the answer can't be the empty run, because best_max is itself a valid candidate that is at least 0. And if the smallest run happens to be the whole array, every real wrap is worth at most 0, so the wrap candidate of 0 loses harmlessly.

⚠️ Don't double the array. Running Kadane on nums + nums does see the wrapped runs, but it can also use an element twice. On [5, -3, 5] it scans [5, -3, 5, 5, -3, 5] and returns 14, the sum of all six cells, with every element counted twice. Doubling only works if you also cap the run length at n, which needs more machinery than Kadane.

Your turn: predict max_circular for [8, -1, -3, 8] and for [-5, -2, -7]. For each one, what would the unguarded max(best_max, total - best_min) return?

Move 5: When two negatives make a positive

Smell: products instead of sums, and signs can flip.

LeetCode 152: Maximum Product Subarray asks for the largest product of a non-empty contiguous run. Values are between −10 and 10, the length is at most 2 × 10⁴, and every run's product fits in a 32-bit integer.

Predict first: replace + with * in max_subarray. What does it return on [2, 3, -2, -3]? The true answer is 36, the whole array.

Sums had a clean rule: a negative run never helps what comes after it. Products don't. A very negative product is one negative factor away from a very positive one. So the notebook needs two numbers: the largest and the smallest product of a run ending here.

def max_product(nums):
    hi = lo = best = nums[0]    # largest / smallest product of a run ending here
    for i in range(1, len(nums)):
        x = nums[i]
        candidates = (x, hi * x, lo * x)            # start fresh, or extend either run
        hi, lo = max(candidates), min(candidates)   # both from the OLD hi and lo
        best = max(best, hi)
    return best

The −12 kept in lo at index 2 becomes 36 at index 3. Zeros need no special case: after a 0, both "extend" candidates are 0, so the next element either starts fresh or the value stays 0. It's O(n) time and O(1) extra space.

Why three candidates are enough. Every run ending at i is x alone, or x times a run ending at i − 1. If x > 0, the largest such product comes from hi. If x < 0, it comes from lo. If x = 0, it is 0 either way. The smallest product works the same way with the roles mirrored.

⚠️ Update both from the old values. Written as two separate statements,

hi = max(x, hi * x, lo * x)
lo = min(x, hi * x, lo * x)    # BUG: uses the hi just computed

the second line sees the new hi. On [2, 3, -2, -3], lo becomes −6 instead of −12 at the −2, and the function returns 18 instead of 36. A tuple assignment evaluates its whole right-hand side before storing anything, which is why the version above is safe. Another common version swaps hi and lo when x is negative and then updates each from its own candidate; it's equivalent.

Your turn: predict max_product for [-2, 3, -4] and for [-2, 0, -1], and write down hi and lo after each step.

Move 6: The biggest swing

Smell: "largest absolute sum", where the answer might be a big gain or a big loss.

LeetCode 1749: Maximum Absolute Sum of Any Subarray asks for the largest |sum| of any run. The empty run, with absolute sum 0, is allowed.

You could run Kadane twice, once for the largest run and once for the smallest, and return max(best_max, -best_min). Move 2 gives a shorter route. As in Move 2, the run from i to j sums to prefix[j + 1] − prefix[i], so its absolute value is the distance between two readings of the running total. The two readings farthest apart are the highest and the lowest, and the absolute value doesn't care which one came first.

def max_absolute_sum(nums):
    running = high = low = 0      # prefix sums, starting with the empty prefix 0
    for x in nums:
        running += x
        high = max(high, running)
        low = min(low, running)
    return high - low

On [2, -5, 1, -4, 3, -2] the running totals are 0, 2, −3, −2, −6, −3, −5. The highest is 2 and the lowest is −6, so the answer is 8, from [-5, 1, -4]: the fall from 2 down to −6. The largest run alone is worth only 3. This is O(n) time and O(1) extra space.

Compare it with Move 2. There, order mattered (buy before you sell), so you subtracted the lowest earlier reading. Here any pair counts, so the overall high and low are enough. Keeping the empty prefix 0 in both is what lets a run start at index 0.

Boss level: Grenander's rectangle

The problem was born two-dimensional: find the rectangle of a grid with the largest sum. Kadane handles that with one more loop. Fix a top row and a bottom row, then add up each column's cells between them. That turns the band into a 1-D array, and its best run is the best rectangle spanning exactly those rows.

def max_rectangle(grid):
    rows, cols = len(grid), len(grid[0])
    best = grid[0][0]
    for top in range(rows):
        col_sums = [0] * cols                # column totals over rows top..bottom
        for bottom in range(top, rows):
            for c in range(cols):
                col_sums[c] += grid[bottom][c]
            best = max(best, max_subarray(col_sums))
    return best

Take this grid:

 4  -6  -2  -2
-4   1   6  -6
 2   4   5  -2

The answer is 16: rows 1–2, columns 1–2, which is 1 + 6 + 4 + 5. No single row gets past 11.

Cost. There are R(R+1)/2 row pairs for R rows and C columns. Each pair costs O(C) to update the column sums and run Kadane, for O(R²·C) time and O(C) extra space. Checking every rectangle with a 2-D prefix-sum table would be O(R²·C²). If R > C, loop over pairs of columns instead, so the squared factor is the smaller side: O(min(R, C)² · max(R, C)).

A harder cousin, LeetCode 363: Max Sum of Rectangle No Larger Than K, uses the same row-pair collapse. It then needs a sorted structure instead of Kadane, because "the largest sum that is at most k" can't be tracked with a running maximum.

Final round: no label on the problem

Challenge 1: which move?

Name the technique for each problem before you open the answer. Values can be negative unless stated otherwise.

1. A ring of 8 checkpoints, each with a signed score. Choose consecutive checkpoints around the ring, each at most once, to maximize the total.
2. The largest total over exactly 30 consecutive days.
3. A game multiplies your score by every card in one consecutive run of cards. Cards are integers from −3 to 3. What is the largest possible multiplier?
4. How many runs of days have a total of exactly 0?
5. The largest swing, up or down, of a bank balance over any stretch of consecutive days, given the daily changes.
6. The brightest rectangle in a grid of signed pixel values.

Challenge 2: one deletion allowed

LeetCode 1186: Maximum Subarray Sum with One Deletion: choose a run, optionally delete one element from it, and maximize the sum. What is left must be non-empty. n is at most 10⁵ and values are between −10⁴ and 10⁴. For example, [1, -2, 0, 3] gives 4: delete the −2 from the whole array.

One number about the past is no longer enough. Design the notebook, write the function in O(n) time and O(1) extra space, and predict the answer for [2, -1, -4, 3, -2, 4].

def maximum_sum(arr):
    keep = best = arr[0]         # best run ending here, no deletion used
    dropped = float('-inf')      # best run ending here, one deletion used
    for i in range(1, len(arr)):
        x = arr[i]
        dropped = max(dropped + x, keep)   # extend a run that already deleted, or delete x
        keep = max(x, keep + x)            # plain Kadane
        best = max(best, keep, dropped)
    return best

Cheat sheet

Before moving on, open a blank editor and solve LeetCode 918 from scratch. Say out loud what max_here and min_here mean at a specific index, why a wrapping run is the total minus the smallest run, which input makes the unguarded formula lie, and why doubling the array doesn't work. If you can do that, every variant in this lesson is the same idea with a different notebook.

Next: Longest Substring Without Repeats for a problem where a sliding window is the right tool, Dynamic Programming Mastery for the "state ending here" idea in general, and Prefix, Suffix & Range Updates for more prefix-sum decompositions.