Kadane's max subarray

O(n)

Kadane's algorithm finds the maximum sum of any contiguous subarray in a single linear pass. It keeps a running sum of the current window; at each element it asks a simple question — is the running sum still pulling its weight? If the sum has dropped to zero or below, the prefix can only hurt, so it's discarded and a new window starts at the current element. Otherwise the element extends the window. The best running sum ever seen is the answer. It's a textbook example of dynamic programming distilled to two variables, and it powers problems from stock-profit windows to image and signal analysis. Try editing in some negative numbers to see the window reset.

Array
Edit the input and press Play

How it works

  1. Walk left to right, keeping a running sum of the current window.
  2. If the running sum drops to zero or below, drop it and start fresh at this element.
  3. Otherwise add the element to the window.
  4. Track the best running sum seen — that slice is the maximum subarray (highlighted).

Pseudocode

1kadane(a):                          # O(n)2  cur ← 0, best ← −∞3  for each x in a:4    if cur ≤ 0: cur ← x              # drop a spent prefix5    else: cur ← cur + x6    best ← max(best, cur)7  return best                        # max contiguous-subarray sum