Maximum subarray (Kadane)

Dynamic programming

Find the contiguous range with the largest sum in one pass: whenever the running sum turns negative, drop it and start over.

In an array of positive and negative numbers (say, daily price changes), find the contiguous range with the largest sum.

Read the full explanation ↓

Time: O(n)
Space: O(1)
CLRS, section 4.1

Input:

n=16PDF export

Sixteen daily price changes; the best range is a[7..10] with sum 43.

def max_subarray(a):
best = a[0]
best_lo = 0
best_hi = 0
cur = a[0]
cur_lo = 0
for i in range(1, len(a)):
if cur < 0:
cur = a[i]
cur_lo = i
else:
cur = cur + a[i]
if cur > best:
best = cur
best_lo = cur_lo
best_hi = i
return best, best_lo, best_hi

Invariant: cur is the largest sum of a subarray ending exactly at i, and best is the largest sum of any subarray up to i.

Start

Local variables

Orange = changed in this step

`a` list

13-3-2520-3-16-231820-712-5-2215-47

Call stack

max_subarray()line 1

Step 1 of 79

How the work grows with input size

Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

comparisons
current input (n=16)

Show as a table

n	comparisons
4	6
6	10
8	14
10	18
12	22
14	26
16	30

Explanation

The problem

In an array of positive and negative numbers (say, daily price changes), find the contiguous range with the largest sum.

Kadane's idea

For each position i, cur is the largest sum of a subarray that ends exactly at i. It has two choices: continue the previous subarray with a[i], or start over from a[i]. If cur is negative, continuing only hurts, so we start over. best is the largest cur seen so far.

Cost

One pass: O(n) time and O(1) memory. CLRS solves the same problem with divide and conquer in O(n log n); Kadane shows that a dynamic-programming idea makes it linear.

What to watch in the trace

The blue band is the best range so far; the cur_lo arrow is where the current run started, and i is the current position.
On "starting over", watch cur_lo jump forward after the big drop.