Kadane's Algorithm

Question 1

What decision does Kadane's algorithm make at each element?

Accepted Answer

Extend current OR start new — At each position i, we choose: currentSum = max(arr[i], currentSum + arr[i])

Question 2

What does Kadane's algorithm compute?

Accepted Answer

Max-sum contiguous subarray — Kadane's finds the maximum-sum contiguous subarray in O(n) time and O(1) space using a running best-ending-here value.

Question 3

The core Kadane recurrence for the best subarray ending at index i is…

Accepted Answer

max of a[i] alone or extend — Either extend the previous subarray (cur + a[i]) or start fresh at a[i], whichever is larger. The global answer is the max of cur over all i.

Question 4

What are Kadane's time and space complexities?

Accepted Answer

O(n) time, O(1) space — A single pass updates two scalars (current and best), so it runs in O(n) time with O(1) extra space.

Question 5

How must Kadane's handle an array where ALL elements are negative?

Accepted Answer

Return the maximum — If the empty subarray is not allowed, the answer is the largest single element. Initializing best to −∞ (not 0) and starting cur = a[i] handles this correctly.

Question 6

Why does resetting the running sum to the current element when it would go negative work?

Accepted Answer

A negative prefix can only reduce a sum — If the best sum ending before i is negative, carrying it forward only hurts; starting fresh at a[i] dominates. That greedy reset is the heart of Kadane's optimality.

Question 7

Kadane's is often described as a dynamic-programming algorithm because…

Accepted Answer

Defined via the previous index value — It's DP collapsed to O(1) space: the optimal subarray ending at i depends only on the optimal subarray ending at i-1, a textbook recurrence.

Question 8

A divide-and-conquer maximum-subarray solution runs in…

Accepted Answer

O(n log n) per recursion level — Split, solve halves, and compute the best crossing subarray in O(n) per level over log n levels: O(n log n) — slower than Kadane's O(n) but a classic recursion exercise.

Question 9

To also report the START and END indices of the maximum subarray, you…

Accepted Answer

Track resets, record bounds — When cur restarts at a[i], set tentativeStart=i. Whenever cur exceeds best, record start=tentativeStart and end=i.

Question 10

The 'maximum PRODUCT subarray' variant differs because…

Accepted Answer

Neg times neg can be large — Negatives flip sign, so the smallest (most negative) product can become the largest after another negative. Track current max and min and swap them when the element is negative.

Kadane's Algorithm

Kadane in one pass

Test your knowledge

What decision does Kadane's algorithm make at each element?

The short version

In more depth

The Core Insight

Why It Works

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?