0

Kadane (Maximum Subarray)

Medium

At every index decide whether to extend the previous best subarray or start fresh from here.

dynamic programminglinear
TimeO(n)
SpaceO(1)
InputComma separated numbers, include negatives
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
current-2best-2

Best subarray ending at index 0 is just -2.

cur-2best-2
1 / 14
cur = a[0]; best = a[0]
for i from 1 to n-1:
cur = max(a[i], cur + a[i])
best = max(best, cur)
Why it matters

The simplest real DP: one state, one transition, two variables.

Practise this
Maximum SubarrayMMaximum Product SubarrayMMaximum Sum Circular SubarrayM
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Memoisation vs Brute Force
O(2^n) naive, O(n) memoised
0/1 Knapsack
O(n * W)
Longest Common Subsequence
O(n * m)
Coin Change
O(coins * amount)
Longest Increasing Subsequence
O(n log n)
Minimum Path Sum
O(rows * cols)
Edit Distance
O(n * m)
Next visualiser
Prefix Sum & Subarray Count