VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.9 of 16 in this moduleFree

Maximum Subarray

The contiguous block with the largest sum: from O(n³) all-pairs, to O(n²) with running sums, to Kadane's O(n) extend-or-restart scan, explained as the stock problem on prefix sums. Then indices, circular arrays, all-negative inputs and the 2D version.

about 10 min 7 Python examples 2 quick checks

Problem. Given nums, find the contiguous subarray (at least one element) with the largest sum, and return that sum.

text
[-2, 1, -3, 4, -1, 2, 1, -5, 4]   →   6     (4 + -1 + 2 + 1)
[5, 4, -1, 7, 8]                   →   23    (the whole array)
[-3, -1, -2]                       →   -1    (just -1)

ML context. "The best contiguous stretch" shows up as the window of a training run with the largest total improvement, the most anomalous stretch of a time series (after subtracting a baseline), or the strongest region of a 1D signal. The 2D version finds the brightest rectangle in an image or a heatmap.

This lesson connects two earlier ideas: prefix sums (lesson 1.2) and the running minimum from the stock problem (lesson 1.4). Kadane's algorithm is what you get when you combine them.


1. Step 1: Clarify

Question Answer Why it matters
Contiguous? Yes Otherwise just add every positive number
Empty subarray allowed? No, at least one element Decides the answer for all-negative input
Values? Negative, zero, positive Negatives are what make it hard
n? Up to 10⁵ O(n²) = 10¹⁰: too slow
Return the sum or the indices? The sum (indices later) Indices need one more variable

2. Step 2: Brute force

Try every start i and every end j, and add up the block.

python
def max_subarray_cubic(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        for j in range(i, n):
            best = max(best, sum(nums[i:j + 1]))     # O(n) sum inside two loops
    return best


assert max_subarray_cubic([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray_cubic([-3, -1, -2]) == -1
print("brute force works: O(n³) time")

O(n³): about n³/6 additions. At n = 10⁵ that's over 10¹⁴. Hopeless.


3. Step 3: Optimise, one waste at a time

Optimisation 1: reuse the running sum (O(n²))

The waste: sum(nums[i:j + 1]) recomputes from scratch, although it's just the previous sum plus nums[j].

python
def max_subarray_quadratic(nums):
    best = nums[0]
    for i in range(len(nums)):
        running = 0
        for j in range(i, len(nums)):
            running += nums[j]                # extend by one element: O(1)
            best = max(best, running)
    return best


assert max_subarray_quadratic([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
print("running sum version: O(n²) time, O(1) space")

O(n²): at n = 10⁵, 5 × 10⁹ steps. Still too slow. We need one pass.

Optimisation 2: Kadane's algorithm (O(n))

First principles. Look at the best subarray that ends at index i. It either:

  • is just nums[i] on its own, or
  • extends the best subarray ending at i − 1 by nums[i].

So cur = max(nums[i], cur + nums[i]). In words: if the running sum so far is negative, it can only hurt what comes next, so drop it and restart. The answer is the best cur seen at any index.

nine frames over [-2, 1, -3, 4, -1, 2, 1, -5, 4]; the running sum restarts at 1 and again at 4, grows to 6 over 4, -1, 2, 1, and the best stays 6.
Diagram— nine frames over [-2, 1, -3, 4, -1, 2, 1, -5, 4]; the running sum restarts at 1 and again at 4, grows to 6 over 4, -1, 2, 1, and the best stays 6.
python
import random


def max_subarray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)                 # extend, or restart at x
        best = max(best, cur)
    return best


def brute(nums):
    return max(sum(nums[i:j + 1]) for i in range(len(nums)) for j in range(i, len(nums)))


assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray([5, 4, -1, 7, 8]) == 23
assert max_subarray([-3, -1, -2]) == -1
rng = random.Random(19)
for _ in range(1000):
    nums = [rng.randint(-10, 10) for _ in range(rng.randint(1, 15))]
    assert max_subarray(nums) == brute(nums)
print("Kadane: O(n) time, O(1) space, matches brute force on 1,000 cases")
  • Time: O(n). Space: O(1).
  • Starting from nums[0], not 0, is what makes all-negative arrays return the largest single value instead of 0.

Why this is the stock problem again

Write prefix sums P[0] = 0, P[k + 1] = P[k] + nums[k]. The sum of nums[i..j] is P[j + 1] − P[i]. So the best subarray is the largest rise from an earlier prefix to a later one: buy low, sell high, exactly lesson 1.4.

the prefix sums [0, -2, -1, -4, 0, -1, 1, 2, -3, 1]; the lowest earlier prefix is -4 at index 3 and the later high is 2 at index 7, so the best sum is 2 − (−4) = 6.
Diagram— the prefix sums [0, -2, -1, -4, 0, -1, 1, 2, -3, 1]; the lowest earlier prefix is -4 at index 3 and the later high is 2 at index 7, so the best sum is 2 − (−4) = 6.
python
import random


def max_subarray_prefix(nums):
    lowest_prefix = 0                         # P[0]
    prefix = 0
    best = nums[0]
    for x in nums:
        prefix += x                           # P[j + 1]
        best = max(best, prefix - lowest_prefix)
        lowest_prefix = min(lowest_prefix, prefix)
    return best


def kadane(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


rng = random.Random(20)
for _ in range(1000):
    nums = [rng.randint(-10, 10) for _ in range(rng.randint(1, 15))]
    assert max_subarray_prefix(nums) == kadane(nums)
print("prefix-sum view agrees with Kadane: two names for one idea")

Notice the order: we compute best before updating lowest_prefix, so the subarray is never empty. Kadane's "restart when negative" is the moment a new lowest prefix appears.

Quick check

In Kadane's algorithm, why do we restart when the running sum becomes smaller than the current value?

  1. To save memory
  2. A negative running sum only lowers any subarray that continues from it, so starting fresh at the current value is never worse
  3. Because the array is sorted
  4. To handle zeros
Show the answer

B. A negative running sum only lowers any subarray that continues from it, so starting fresh at the current value is never worse — The best subarray ending at i either extends the best one ending at i − 1 or starts at i; a negative prefix makes extending worse.


4. When the constraints change

a decision map: all pairs with prefix sums for small inputs, Kadane for the classic problem, Kadane with a start marker for indices, total minus the minimum subarray for circular arrays, and row pairs plus Kadane for the 2D version.
Diagram— a decision map: all pairs with prefix sums for small inputs, Kadane for the classic problem, Kadane with a start marker for indices, total minus the minimum subarray for circular arrays, and row pairs plus Kadane for the 2D version.

Change A: return the indices, not just the sum

Remember where the current run started, and copy it when best improves.

python
def max_subarray_indices(nums):
    cur, start = nums[0], 0
    best, best_lr = nums[0], (0, 0)
    for i in range(1, len(nums)):
        if nums[i] > cur + nums[i]:
            cur, start = nums[i], i           # restart here
        else:
            cur += nums[i]
        if cur > best:
            best, best_lr = cur, (start, i)
    return best, best_lr


best, (l, r) = max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4])
assert best == 6 and (l, r) == (3, 6)
print("indices:", (l, r), "still O(n) time, O(1) space")

Change B: the array is circular

The best block either doesn't wrap (plain Kadane) or wraps around the end. A wrapping block is everything except some middle block, so its sum is total − (minimum subarray). One catch: if every value is negative, "everything except the minimum" would be empty, so fall back to plain Kadane.

python
import random


def kadane(nums, sign=1):
    cur = best = sign * nums[0]
    for x in nums[1:]:
        cur = max(sign * x, cur + sign * x)
        best = max(best, cur)
    return sign * best                        # sign = -1 finds the minimum subarray


def max_circular(nums):
    straight = kadane(nums)
    if straight < 0:
        return straight                       # all negative: wrapping can't help
    return max(straight, sum(nums) - kadane(nums, -1))


def brute_circular(nums):
    n = len(nums)
    return max(sum(nums[(i + k) % n] for k in range(length))
               for i in range(n) for length in range(1, n + 1))


assert max_circular([5, -3, 5]) == 10        # 5 + 5 across the end
rng = random.Random(21)
for _ in range(500):
    nums = [rng.randint(-8, 8) for _ in range(rng.randint(1, 10))]
    assert max_circular(nums) == brute_circular(nums)
print("circular version: O(n) time, O(1) space")

Change C: the empty subarray is allowed

Then the answer is never negative: start best at 0 instead of nums[0] (or return max(0, kadane(nums))). One line, but it must be asked in the clarify step; it changes the answer for all-negative input.

Change D: the best rectangle in a 2D grid

Fix a pair of rows (top, bottom), collapse the columns between them into one array of column sums, and run Kadane on it. With r rows and c columns: O(r² · c) instead of O(r³ · c³) for every rectangle.

python
import random


def kadane(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


def max_rectangle(grid):
    rows, cols = len(grid), len(grid[0])
    best = grid[0][0]
    for top in range(rows):
        col_sums = [0] * cols
        for bottom in range(top, rows):
            for c in range(cols):
                col_sums[c] += grid[bottom][c]      # add one more row: O(c)
            best = max(best, kadane(col_sums))
    return best


def brute_rect(grid):
    R, C = len(grid), len(grid[0])
    return max(sum(grid[r][c] for r in range(r1, r2 + 1) for c in range(c1, c2 + 1))
               for r1 in range(R) for r2 in range(r1, R) for c1 in range(C) for c2 in range(c1, C))


rng = random.Random(22)
for _ in range(200):
    grid = [[rng.randint(-5, 5) for _ in range(rng.randint(1, 5))] for _ in range(1)]
    grid += [[rng.randint(-5, 5) for _ in range(len(grid[0]))] for _ in range(rng.randint(0, 4))]
    assert max_rectangle(grid) == brute_rect(grid)
print("2D version: O(r² · c) with Kadane inside")

The full table

If the constraint becomes… Best approach Time Space
Teaching or tiny n Running sums over all starts O(n²) O(1)
Classic Kadane O(n) O(1)
Return the indices Kadane + start marker O(n) O(1)
Empty allowed Kadane with best starting at 0 O(n) O(1)
Circular array max(Kadane, total − min subarray) O(n) O(1)
Exactly length k Sliding window sum (module 2) O(n) O(1)
Many range-sum queries Prefix sums (lesson 1.2) O(1) per query O(n)
2D best rectangle Row pairs + Kadane on column sums O(r² · c) O(c)
Maximum product subarray Track max and min (a negative flips them) O(n) O(1)

Quick check

For a circular array, why is the best wrapping subarray equal to total − (minimum subarray)?

  1. A block that wraps around the end is everything except one contiguous middle block, so maximising it means removing the smallest middle block
  2. Because circular arrays are sorted
  3. Because Kadane can't handle negatives
  4. It's only an approximation
Show the answer

A. A block that wraps around the end is everything except one contiguous middle block, so maximising it means removing the smallest middle block — Complement thinking: a wrapping block plus a middle block is the whole array.


5. Saying it out loud

"Brute force sums every block: O(n³); a running sum makes it O(n²). The best block ending at i either extends the best block ending at i − 1 or starts fresh, so I keep a running sum and restart whenever it's worse than the value alone: Kadane, O(n) time, O(1) space. It's the stock problem on prefix sums. For a circular array I'd also try total minus the minimum subarray; for 2D, fix two rows and run Kadane on column sums."


Check yourself

  1. Where does the O(n³) → O(n²) improvement come from?
  2. State Kadane's recurrence and the intuition for restarting.
  3. Why initialise with nums[0] rather than 0?
  4. How does Kadane relate to prefix sums and the stock problem?
  5. How do you handle a circular array, and what's the all-negative catch?
  6. How does the 2D version reuse Kadane?
Answers
  1. Each block's sum is the previous block's sum plus one element, so the innermost sum disappears.
  2. cur = max(x, cur + x); a negative running sum can only lower whatever follows, so drop it.
  3. So all-negative inputs return the largest single value (at least one element is required).
  4. Block sums are differences of prefix sums; the best block is the largest rise from an earlier low prefix, exactly the one-trade stock problem.
  5. Take the max of plain Kadane and total − minimum subarray; if every value is negative, return plain Kadane, since the complement would be empty.
  6. Fix a top and bottom row, sum the columns between them into one array, and run Kadane: O(r² · c).