Kadane's Algorithm and Maximum Subarray

Maximum Subarray Sum is one of the most-asked interview questions, and Kadane's algorithm is its elegant O(n) answer. It is the canonical example of "local optimal choice → global optimum" and a gentle on-ramp to dynamic programming.

The core idea

Walk left to right keeping curMax = the best subarray sum ending at the current index. At each element choose to extend the previous subarray or start fresh:
curMax = max(arr[i], curMax + arr[i]); then globalMax = max(globalMax, curMax).
The insight: if the running sum ever goes negative, it can only hurt what comes next, so drop it and restart. One pass, O(1) memory.

Variant	Time	Space	Note
Kadane (max sum)	O(n)	O(1)	classic
Track indices	O(n)	O(1)	remember start/end
Max product subarray	O(n)	O(1)	track min & max
All-negative array	O(n)	O(1)	answer = max element
Circular max subarray	O(n)	O(1)	max(kadane, total − minKadane)

Exam Tricks & Tips

• 🎯 Initialise curMax = globalMax = arr[0], then loop from index 1 — handles all-negative arrays correctly.
• 🎯 Max product subarray needs both running max and min, because negative × negative flips to large positive.
• 🎯 Circular version: answer = max(normal Kadane, totalSum − minSubarraySum); guard the all-negative case.
• 🎯 To return the subarray itself, record start when you restart and end when globalMax updates.
• 🎯 It's really DP: dp[i] = max(arr[i], dp[i-1]+arr[i]) collapsed to O(1) space.
• ❌ Common mistake: initialising globalMax = 0 — that returns 0 for an all-negative array instead of the largest element.

Expected pattern

"Maximum subarray sum", "max product subarray", or a circular twist. Interviewers expect the O(n) one-pass solution and correct handling of the all-negative edge case.

Quick recap

Kadane: curMax = max(arr[i], curMax+arr[i]), globalMax tracks the best — O(n)/O(1). Init from arr[0], not 0. Products need min & max; circular arrays subtract the minimum subarray from the total.

Cover the answer, recall, then check. 11 cards on Kadane's algorithm.

Q1. Kadane's core recurrence?
A1. curMax = max(arr[i], curMax + arr[i]); globalMax = max(globalMax, curMax).

Q2. Time and space complexity?
A2. O(n) time, O(1) space — a single pass.

Q3. Why initialise from arr[0], not 0?
A3. globalMax = 0 wrongly returns 0 for an all-negative array; the correct answer is the largest (least-negative) element.

Q4. Intuition for dropping a negative running sum?
A4. A negative prefix can only reduce any future subarray's total, so restarting from the current element is never worse.

Q5. How does Kadane relate to DP?
A5. dp[i] = max(arr[i], dp[i-1]+arr[i]); only dp[i-1] is needed, so it collapses to one variable — O(1) space.

Q6. Max product subarray — what extra state is needed?
A6. Track running max AND min; multiplying two negatives yields a large positive, so swap them on a negative element.

Q7. Circular maximum subarray formula?
A7. max(standard Kadane, totalSum − minSubarraySum); special-case when all elements are negative.

Q8. How to recover the actual subarray indices?
A8. Record a tentative start when curMax resets to arr[i]; commit start/end whenever globalMax updates.

Q9. Answer for [-3, -1, -4]?
A9. −1 — the maximum single element, since every subarray sum is negative.

Q10. Does Kadane work with all-positive arrays?
A10. Yes — it sums the whole array, which is the maximum subarray.

Q11. Most common Kadane bug?
A11. Resetting curMax to 0 instead of arr[i], breaking all-negative inputs and mislabeling subarray starts.

"Find the contiguous subarray with the largest sum" is a rite-of-passage interview question, and Kadane's algorithm answers it in a single O(n) pass with O(1) memory — a beautiful example of dynamic programming compressed to two variables.

Core idea: as you scan left to right, ask at each element one local question — "is it better to extend the best subarray ending here, or start fresh at this element?" The global answer is the best of all these local bests.

How it works

Beginner — the running best

Track cur = the largest sum of a subarray ending at the current index, and best = the largest seen anywhere.

cur = best = a[0]
for i in 1..n-1:
    cur = max(a[i], cur + a[i])   # start fresh vs extend
    best = max(best, cur)
return best

One pass, constant memory → O(n) time, O(1) space.

Intermediate — why the greedy choice is optimal

cur + a[i] extends the previous best-ending-here; a[i] alone abandons it. If cur is negative, dragging it forward only hurts, so we drop it — that is the DP recurrence dp[i] = max(a[i], dp[i-1] + a[i]). Kadane just stores dp[i-1] in one variable. The answer is max(dp[i]), not dp[n-1], so we track best separately.

Advanced — variants and edge cases

• All-negative arrays: initialise best = a[0] (not 0), or you will wrongly return 0 for an empty subarray. This is the most-tested edge case.
• Recover the indices: remember where cur reset (start) and where best improved (bestStart..i).
• Maximum-product subarray: track both a running max and min, because a negative times a negative can flip the min into the new max.
• Circular maximum subarray: answer is max(normalKadane, totalSum − minSubarray), handling the wrap-around.

Worked example

[-2, 1, -3, 4, -1, 2, 1, -5, 4]. Trace cur: -2, 1, -2, 4, 3, 5, 6, 1, 5. The peak cur is 6, from the subarray [4, -1, 2, 1]. best = 6. Notice cur reset to 1 at index 1 (dropping -2) and to 4 at index 3 (dropping the negative run) — those resets are the algorithm's whole intelligence.

When to use it

Any "maximum/minimum sum (or product) of a contiguous subarray" prompt. Recognise it when a problem reduces to "best running total with the option to restart". If the subarray must be non-contiguous, it is a different (usually simpler) problem — just sum the positives.

Tricks & gotchas

• Seed with a[0], never 0, unless empty subarrays are explicitly allowed.
• The moment cur goes negative, the next element will restart it — that is expected.
• Mnemonic: "Extend or restart — keep the best you've ever seen."

Key formulas

• Recurrence: best_ending_here = max(a[i], best_ending_here + a[i]); answer = max over all i.
• Time O(n), space O(1).
• Handles negative numbers; if all negative, answer = maximum single element.
• Maximum subarray sum is a classic DP with O(1) state.
• Circular max subarray = max(normal Kadane, total − minimum subarray) (unless all negative).

Usage: track the running best-ending-here sum and reset when it turns negative.

Worked Example

Problem: Find the maximum contiguous subarray sum of [-2, 1, -3, 4, -1, 2, 1, -5, 4] using Kadane's algorithm.

Solution: Keep cur = best sum ending at the current element, and best = best seen so far. At each element: cur = max(x, cur + x).

x	cur = max(x, cur+x)	best
-2	-2	-2
1	max(1, -1) = 1	1
-3	max(-3, -2) = -2	1
4	max(4, 2) = 4	4
-1	max(-1, 3) = 3	4
2	max(2, 5) = 5	5
1	max(1, 6) = 6	6
-5	max(-5, 1) = 1	6
4	max(4, 5) = 5	6

The best sum is 6, from the subarray [4, −1, 2, 1].

Kadane runs in a single pass → O(n) time, O(1) space.

Answer: Maximum subarray sum = 6.