Problem. Given nums, find the contiguous subarray (at least one element) with the largest sum, and return
that sum.
[-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.
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].
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 − 1bynums[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.
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.
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?
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
Change A: return the indices, not just the sum
Remember where the current run started, and copy it when best improves.
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.
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.
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)?
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
- Where does the O(n³) → O(n²) improvement come from?
- State Kadane's recurrence and the intuition for restarting.
- Why initialise with
nums[0]rather than 0? - How does Kadane relate to prefix sums and the stock problem?
- How do you handle a circular array, and what's the all-negative catch?
- How does the 2D version reuse Kadane?
Answers
- Each block's sum is the previous block's sum plus one element, so the innermost sum disappears.
cur = max(x, cur + x); a negative running sum can only lower whatever follows, so drop it.- So all-negative inputs return the largest single value (at least one element is required).
- 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.
- Take the max of plain Kadane and total − minimum subarray; if every value is negative, return plain Kadane, since the complement would be empty.
- Fix a top and bottom row, sum the columns between them into one array, and run Kadane: O(r² · c).