Maximum Subarray (Kadane)

Find the contiguous subarray with the largest sum. Keep a running sum; whenever it drops to zero or below, a fresh start beats carrying the deficit forward.

Category

Dynamic Programming

Time complexity

O(n)

Space complexity

O(1)

Pseudocode

cur ← 0
if cur ≤ 0: restart cur = a[i]
else: cur += a[i]
best ← max(best, cur)

Reference implementation

cur = best = a[0]
for x in a[1:]:
    cur = max(x, cur + x)
    best = max(best, cur)

Open the interactive Maximum Subarray (Kadane) visualisation →