DPAlgorithmaka maximum subarray, max sum contiguous subarray

Kadane's Algorithm

Find the maximum-sum contiguous subarray in one pass by tracking the best sum ending at each position.

▶ Visualize Pattern: Dynamic Programming Practice (1)

Progress

Overview

Given an array of integers (possibly negative), find the contiguous subarray with the largest sum. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6 from [4, -1, 2, 1]. Kadane's algorithm solves it in O(n) time and O(1) space.

It is a DP with a one-element state: "best sum of a subarray that ends exactly here". Because that state depends only on the previous position, the whole table collapses to a running variable. The same idea, with different combining rules, gives maximum product subarray, maximum circular subarray, and best-time-to-buy-and-sell-stock.

1D DPsubarrayO(n)O(1) spaceprefix reset

Intuition

A mental model before the formal terms.

Walk the array left to right carrying a running sum. At each element ask: "does the stuff I am carrying help me, or would I be better off starting fresh here?" If the carried sum is negative it can only drag the next element down, so drop it. For [-2, 1, -3, 4, …]: carry -2 → start fresh at 1 → 1 + (-3) = -2 → negative, so start fresh at 4 → 4 - 1 = 3 → 5 → 6 (best so far) → 1 → 5. The best seen was 6.

Equivalently: using Prefix Sum P, the best subarray ending at i is P[i] - min(P[0..i-1]). Kadane tracks that running minimum implicitly through the "reset to zero" rule.

How it works

State: best_ending_here[i] = maximum sum of a non-empty subarray whose last element is nums[i].
Transition: best_ending_here[i] = nums[i] + max(best_ending_here[i-1], 0) — extend the previous best if it is positive, else start a new subarray at i. Equivalently max(nums[i], best_ending_here[i-1] + nums[i]).
Base case: best_ending_here[0] = nums[0].
Iteration order: i from 1 to n-1.
Answer location: max over i of best_ending_here[i] — tracked as a running best (initialized to nums[0], not 0). The subarray with the global maximum may end anywhere.
Space optimization: only the previous state is read, so a single variable cur replaces the array. To recover the subarray, record the start index when cur resets and the (start, i) pair when best improves.

Why it works

Optimal substructure: any subarray ending at i is either [i, i] alone or a subarray ending at i-1 extended by nums[i]. In the second case the prefix must be the *best* subarray ending at i-1 — otherwise swapping in the better one improves the sum. So the max over these two options is exact, and it reduces to nums[i] + max(prev, 0).

Every subarray ends somewhere, so the global maximum is the max of the per-position maxima; scanning once and keeping the largest value seen finds it.

All-negative edge case: if every element is negative, every cur is negative and the "reset" to nums[i] happens at every step. With best initialized to nums[0] the answer is the largest single element, which is correct for the non-empty version. Initializing best = 0 would silently answer "empty subarray, sum 0" — right only if the problem allows an empty subarray.

Recognition

How to tell a problem wants this.

"Maximum sum contiguous subarray", "largest sum of consecutive elements", "best gain over a window of any length".
Values can be negative (otherwise the whole array is trivially the answer).
A single linear pass is expected (n up to 10^5–10^6).

“number of ways” → Dynamic Programming “maximum subarray sum” → Kadane's Algorithm

Interactive visualization

Play, step, change the input. ← → and space work too.

Array — Positive and negative numbers, up to 40

-2

-3

-1

-5

1/14Maximum subarray sum. cur is the best sum of a subarray ending at the current index; best is the best seen anywhere. Both start at a[0]=-2.

Current subarray (cur)Element being addedBest subarray so farDropped prefix

PseudocodeLearn Kadane's Algorithm →

1cur = a[0], best = a[0], start = 0
2for i in 1 .. n-1:
3  if cur < 0: cur = a[i]; start = i
4  else: cur += a[i]
5  if cur > best: best = cur; bestRange = [start, i]
6return best

Variables

cur-2

best-2

start0

Complexity

best O(n)

avg O(n)

worst O(n)

space O(1)

Speed

Pseudocode

1cur = best = nums[0]
2for i in 1..n-1:
3  cur = max(nums[i], cur + nums[i])
4  best = max(best, cur)
5return best

Implementations

1# Kadane: the maximum-sum contiguous subarray in one pass. The insight is
2# that the best subarray ending at i either extends the best one ending at
3# i-1, or starts fresh at i — so one number carries all the history needed.
4 
5 
61 · best = answer so far, cur = best sum of a subarray ending here
7def max_subarray_sum(a: list[int]) -> int:
8    if not a:
9        return 0  # caller's convention
10    best = cur = a[0]
11    for x in a[1:]:
122 · Extend, or restart at x — whichever is larger
13        cur = max(x, cur + x)
14        best = max(best, cur)
15    return best
16 
17 
183 · Tracking the boundaries costs two extra variables, not another pass
19def max_subarray_range(a: list[int]) -> tuple[int, int, int]:
20    if not a:
21        return 0, -1, -1
22    best = cur = a[0]
23    best_lo = best_hi = cur_lo = 0
24    for i in range(1, len(a)):
25        if cur + a[i] < a[i]:
26            cur = a[i]
27            cur_lo = i  # restarting: the new subarray begins here
28        else:
29            cur += a[i]
30        if cur > best:
31            best, best_lo, best_hi = cur, cur_lo, i
32    return best, best_lo, best_hi
33 
34 
354 · Circular arrays: the answer is either normal, or total minus the minimum
36def max_subarray_circular(a: list[int]) -> int:
37    if not a:
38        return 0
39    total = max_cur = max_best = min_cur = min_best = a[0]
40    for x in a[1:]:
41        total += x
42        max_cur = max(x, max_cur + x)
43        max_best = max(max_best, max_cur)
44        min_cur = min(x, min_cur + x)
45        min_best = min(min_best, min_cur)
465 · If every element is negative, total - min_best is 0 (the empty wrap)
47    return max_best if max_best < 0 else max(max_best, total - min_best)

Walkthrough

best = cur = a[0] chains the assignment, which is idiomatic for two variables that start equal.
for x in a[1:] iterates the values directly, but note that the slice *copies* the list — itertools.islice(a, 1, None) avoids that for large inputs.
max_subarray_range uses index iteration because it needs i for the boundaries, and updates all three best values in one tuple assignment.
total = max_cur = max_best = min_cur = min_best = a[0] initialises five variables from one value, which is compact and safe because integers are immutable.
The final conditional expression handles the all-negative case, where the complement of the minimum subarray is empty.

Complexity (this implementation)

time O(n) · space O(1) for the sums; O(n) for the `a[1:]` slice copy

The slice in the loop header is the one place this version allocates; islice removes it without changing the shape of the code.

Language notes

a[1:] copies; itertools.islice(a, 1, None) is the lazy equivalent and matters for large lists.
Chained assignment (a = b = value) evaluates the right-hand side once and binds it to every name — safe for immutable values, aliasing for mutable ones.
Python integers are unbounded, so there is no overflow concern in the accumulators — unlike C++.
max() and min() on two arguments are C-level calls and are fine in a hot loop; max() over a generator is a different cost profile.

Common mistakes in this language

Slicing in the loop header for a very large list and quietly doubling memory.
Initialising best = 0, which is wrong for an all-negative array.
Using chained assignment with a mutable value (a = b = []), which aliases — harmless here because the values are integers.

Language differences that matter here

Accumulator width: C++ needs long long to avoid overflow on long arrays of large values, Python is unbounded, and JS/TS are exact only to 2^53.
Returning three values: C++ uses std::tuple (unpacked with structured bindings), Python a tuple, and JS/TS an object — the object is the only one that resists positional mix-ups.
Iterating "all but the first": C++ indexes from 1, JS/TS index from 1, and Python a[1:] copies unless itertools.islice is used — a hidden allocation the other three do not have.
The empty-input convention has no cross-language standard; every version here documents its choice explicitly rather than assuming.

Complexity

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

The divide-and-conquer alternative is O(n log n); the prefix-sum formulation is also O(n) but needs the running minimum prefix.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Maximum (or minimum) sum contiguous subarray in one pass.
Variants with the same "extend or restart" structure: maximum product subarray (track max and min), maximum circular subarray (total - min subarray), best time to buy and sell stock (differences array).
2D maximum-sum submatrix: fix a pair of rows, collapse columns into a 1D array, run Kadane — O(n²·m).

Avoid it when

The subarray length is constrained (exactly k, at most k) — use Sliding Window (Fixed Size) or prefix sums with a Monotonic Queue.
The problem asks for a sub*sequence* (non-contiguous) — then just sum the positives.
Queries over many ranges — precompute with a Segment Tree storing (sum, best prefix, best suffix, best) per node.

Alternatives

Prefix Sum Divide and Conquer Segment Tree Sliding Window (Variable Size)

Common mistakes

Initializing best = 0 for an all-negative array, returning 0 instead of the largest element.
Resetting cur to 0 instead of to nums[i] — same all-negative bug in another form.
Returning cur (the sum ending at the last element) instead of best.
In the product variant, forgetting that a negative min times a negative number can become the new max.

Interview patterns

Maximum Subarray (Kadane).
Maximum Product Subarray: carry both the max and min product ending here.
Maximum Sum Circular Subarray: max(kadane_max, total - kadane_min), guarding the all-negative case.
Best Time to Buy and Sell Stock: Kadane over daily price differences.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced
Recognizing a dynamic-programming problemAdvanced

Mock interviews

Coin ChangeIntermediate

Example problems

Maximum Subarraymedium

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related