DPDynamic Programming

Kadane's Algorithm

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

Learn Kadane's Algorithm →
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
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
i0
cur-2
best-2
start0
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed