// pattern debugger≡ menu

stack>arrays/ maximum_subarray

// Maximum Subarray (Kadane)

mediumLC #53pattern = arrays

// step through it

click the player, then ◀ ▶ arrow keys step

i
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
step 1/10
Kadane: at each element decide — extend the running subarray, or start fresh here?
current = -2
max = -2

task

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]  →  6   (subarray [4, -1, 2, 1])

how to think

The brute force checks every subarray’s sum — O(n²), or O(n) with a running total per start index, still O(n²) overall. The insight that collapses it to O(n): a subarray ending at index i either extends the best subarray ending at i - 1, or it starts fresh at i, whichever gives a bigger sum. There’s no third option — any subarray ending at i either includes i - 1 or it doesn’t.

That’s a one-variable recurrence: current = max(nums[i], current + nums[i]). If dragging the previous run along would make things worse than starting over, drop it — a negative running sum can never help a future subarray, so there’s no reason to carry it forward. Track the best current has ever been, and that’s the answer.

this is DP

Kadane’s algorithm is dynamic programming — dp[i] = the best sum of a subarray ending exactly at i, with the recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]). The only reason it doesn’t look like the DP pages in Dynamic Programming Basics is that dp[i] only ever depends on dp[i-1], so the whole table compresses to one variable (current). Every 1D DP you’ll meet later starts as a full array and gets compressed the same way once you notice the same thing.

template instance

Single-pass running accumulator skeleton. Invariant: current holds the best sum of a subarray ending exactly at the current index; best holds the best seen anywhere so far. The fold: current = Math.Max(nums[i], current + nums[i]) — extend or restart.

solution

public int MaxSubArray(int[] nums)
{
    int best = nums[0];
    int current = nums[0];

    for (int i = 1; i < nums.Length; i++)
    {
        current = Math.Max(nums[i], current + nums[i]);   // extend the run, or start fresh at i
        best = Math.Max(best, current);
    }
    return best;
}

trace

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], best/current start at nums[0] = -2:

i nums[i] current + nums[i] current = max(nums[i], …) best
1 1 -2 + 1 = -1 max(1, -1) = 1 1
2 -3 1 + -3 = -2 max(-3, -2) = -2 1
3 4 -2 + 4 = 2 max(4, 2) = 4 4
4 -1 4 + -1 = 3 max(-1, 3) = 3 4
5 2 3 + 2 = 5 max(2, 5) = 5 5
6 1 5 + 1 = 6 max(1, 6) = 6 6
7 -5 6 + -5 = 1 max(-5, 1) = 1 6
8 4 1 + 4 = 5 max(4, 5) = 5 6

Final answer: best = 6.

-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
i=2: current sinks to -2 (extending still beats restarting at -3); at i=3 the restart wins — max(4, -2+4=2) = 4 — and the winning run begins
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
[4, -1, 2, 1] sums to 6 — the maximum, found without ever re-summing a subarray from scratch

why it works

Every subarray ending at index i either includes index i - 1 or starts fresh at i — there is no other shape it can take. current after processing i is therefore, by induction, the true best sum among all subarrays ending at exactly i: it’s correct at i = 0 trivially, and the recurrence picks the better of “extend the best-ending-at-i-1” and “start over”, which covers both cases exactly. Since the true global answer must end somewhere, taking the max of current over every i finds it.

time = O(n)
space = O(1)
passes = 1

common bugs

  • Initializing best/current to 0 instead of nums[0] — silently wrong on an all-negative array, where the correct answer is negative but 0 looks like a valid (and larger) subarray sum.
  • Returning current instead of best — current can drop after the true maximum has already passed; only best remembers the peak.
  • Trying to also track which subarray won (start/end indices) without a second pair of variables — current resetting erases the start index unless you snapshot it at the same moment you reset.
  • Confusing this with “maximum subsequence” (elements don’t need to be contiguous) — that’s a different, harder problem; this one requires the elements to be adjacent.

variants you can now solve

  • Best Time to Buy and Sell Stock (LC 121) — track the cheapest price so far and the best profit so far; that’s this same extend-or-reset recurrence with “profit if I sell today” standing in for nums[i].
  • Maximum Product Subarray (LC 152) — the extend-or-restart idea still applies, but a negative number can flip a small product into a large one, so you carry a running min alongside the running max.
  • Maximum Sum Circular Subarray (LC 918) — run Kadane twice: once for the best normal subarray, once for the best “wraparound” subarray via total-minus-minimum.

// related problems