Kadane's Algorithm

Maximum subarray sum in one linear pass

time O(n)space O(1)

The key insight: once your running total goes negative, it can only drag down whatever you add next — so there's never a reason to keep it. At each number, compare 'keep extending my current run' vs. 'give up on it and restart fresh right here', and always take whichever is bigger. One pointer (curr) tracks that running total; a second (best) just remembers the highest curr has ever been. Because a bad run gets abandoned the instant it turns negative, one left-to-right pass is enough — no need to check every possible subarray.

Details

Animated on: Find the contiguous subarray with the largest sum.

Problem:Maximum SubarrayMedium

Maximum subarray sum in one linear pass

step 1 / 10

-2

[0]

[1]

-3

[2]

[3]

-1

[4]

[5]

[6]

-5

[7]

[8]

Seed both curr and best with the first element: curr = best = -2. curr always means 'best subarray sum ending right here'.

i=0· arr[0] = -2

Pseudocode

1FUNCTION maxSubArray(nums):
2  set curr and best both to nums[0]
3  FOR i from 1 to (length of nums) - 1:
4    curr = the larger of nums[i] and (curr + nums[i])
5    best = the larger of best and curr
6  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 10 steps

Seed both curr and best with the first element: curr = best = -2. curr always means 'best subarray sum ending right here'.
curr + nums[i] = -2 + 1 = -1 is worse than nums[i] = 1 alone, so we DROP the -2 and reset. curr = 1, and best rises to 1.
curr + nums[i] = 1 + (-3) = -2 beats -3 alone, so we EXTEND to [1,-3]. curr sinks to -2, but best holds at 1.
nums[i] = 4 beats curr + nums[i] = -2 + 4 = 2, so RESET — abandon [1,-3] and start fresh at 4. curr = 4, best jumps to 4.
curr + nums[i] = 4 + (-1) = 3 beats -1 alone, so EXTEND to [4,-1]. curr = 3; best stays 4 (its best run is still just [4]).
Extend to [4,-1,2]: curr = 3 + 2 = 5. That sets a NEW best — best = 5, and the winning run now spans [4,-1,2].
Extend to [4,-1,2,1]: curr = 5 + 1 = 6. New best = 6 — this is the winning subarray.
curr = 6 + (-5) = 1 still beats -5 alone, so we keep the run alive hoping to recover. curr drops to 1; best is untouched at 6.
curr = 1 + 4 = 5 — the tail [-5,4] rode along (blue) but never beat best = 6. Scan finished with best still 6.
Answer: the maximum subarray is [4,-1,2,1] summing to 6 — return best.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Maximum Subarray in the editor All Arrays problems Back to roadmap