Faangprep Logo
Log inStart free
Browse curriculum

Kadane's Algorithm

Kadane's algorithm finds the maximum subarray sum in O(n) time.

NEW BEST

-2

0

1

1

-3

2

4

3

-1

4

2

5

1

6

-5

7

4

8

Current run

-2

Best so far

-2

 

Add -2 → running sum -2. Best so far: -2.

Next

The run so far was worth ≤ 0, so drop it and restart at 1. Anything a negative prefix touches is better off without it.

Array

Intuition

If the current subarray sum becomes negative, it's better to discard it and start a new subarray from the next element. A negative prefix will only reduce the sum of any future subarray.

Concept

  • Idea: Iterate through the array, adding elements to currentSum.
  • Update Max: If currentSum > maxSum, update maxSum.
  • Reset: If currentSum < 0, reset currentSum to 0 (start fresh).

How it Works

Algorithm:

  1. Initialize currentSum = 0, maxSum = -Infinity.
  2. For each element x in array:
  3. currentSum += x
  4. maxSum = max(maxSum, currentSum)
  5. If currentSum < 0, set currentSum = 0.

Step-by-Step Breakdown

Watch the visualization:

  • Solid blue cell: The element being added to the current run.
  • Pale blue cells with a blue outline: The rest of the current run.
  • Grey, struck-through cells: Elements left behind when the run was reset.
  • Current run and Best so far: The two sums, side by side. At the end the best subarray is drawn solid blue.
  • Notice how the run resets when its sum turns negative.

Trace: A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

A[0] = -2

Nothing precedes it, so the run is -2 and that is also the best seen so far. Seeding the best with the first element, not with 0, is what keeps an all-negative array honest.

cur -2, best -2

A[1] = 1

Extending gives -1, but 1 on its own is larger, so the negative run is abandoned here.

cur 1, best 1

A[2] = -3

Extending gives -2, which beats restarting at -3. The run continues even though it is now negative.

cur -2, best 1

A[3] = 4

Extending gives 2, but 4 alone is larger, so the run restarts. This index is where the answer begins.

cur 4, best 4

A[4] = -1

Extending gives 3, well above restarting at -1. The best stays at 4 because 3 is not an improvement.

cur 3, best 4

A[5] = 2

The run climbs past the recorded best, which moves with it.

cur 5, best 5

A[6] = 1

Still climbing, and the best follows again.

cur 6, best 6

A[7] = -5

The run drops to 1 but survives, since 1 beats restarting at -5. The 6 is already banked and is not at risk.

cur 1, best 6

A[8] = 4

Extending gives 5, short of the 6 already recorded.

cur 5, best 6

result

The answer is A[3..6], which is 4, -1, 2, 1. Recording the index at every restart is what recovers those two bounds rather than just the sum.

6

When to Use

  • Finding the maximum sum contiguous subarray.
  • Stock trading problems (max profit).

When NOT to Use

  • Maximum product subarray: two negatives multiply to a positive, so a negative running product is not safe to discard. Track the running maximum and minimum product instead.
  • Circular arrays: the best subarray may wrap around the end. Run it for the maximum and for the minimum, and take the larger of maxSum and total - minSum (unless every element is negative).
  • A length limit on the subarray: with at most k elements the reset rule no longer holds; use prefix sums with a monotonic deque over the last k positions.

All-negative input is not a reason to avoid it: this version returns the largest single element, because maxSum is updated before currentSum is reset. Swap those two lines, or start maxSum at 0, and it returns 0 instead.

How to Identify

"Maximum subarray sum", "Largest sum contiguous segment".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Prefix Sum

Next

Boyer-Moore Voting

Frequently Asked Questions

Why is it safe to discard a running sum once it turns negative?

A negative prefix can only reduce whatever follows it, so the best subarray ending at the next position never wants to include it. Dropping it and starting fresh therefore loses nothing.

What does it return when every element is negative?

The reset-to-zero form returns 0, which is not a real subarray. Track the running value as max(current + x, x) and initialise the answer to the first element instead, which correctly returns the largest single element.

How do I recover the subarray, not just its sum?

Record the start index whenever you restart the running sum, and whenever you improve the best sum, save that start together with the current position as the best range.