Kadane's Algorithm Explained: Template, Trace and Problems

Kadane's algorithm finds the largest sum of any contiguous subarray in one pass: at each element, either extend the current run or start a new run at that element, and keep the best total seen, which gives O(n) time and O(1) space. Use it when a problem asks for the maximum (or minimum) sum, product or score of a contiguous subarray and the values can be negative.

Below: the template, a step-by-step trace, why it is correct, three worked LeetCode problems (53, 152 and 918), the bugs interviewers watch for and a practice list. Every code block on this page was run in Python with asserts against a brute-force check of all subarrays before we published it.

When to use Kadane's algorithm

• The question says subarray or substring (contiguous), not subsequence.
• You want a maximum or minimum of a sum-like score over all such subarrays.
• Values can be negative. If every value were positive, the whole array would win and you would not need an algorithm.
• There is no fixed window size or target. A fixed size k or "sum equals k" points to the sliding window pattern or the prefix sum pattern instead.
• The prompt hints at O(n) time. Brute force over all subarrays is O(n²); Kadane is the standard way down to O(n).

How Kadane's algorithm works

Keep two numbers while you scan left to right:

• curr: the best sum of a subarray that ends exactly at the current index.
• best: the best sum of any subarray seen so far.

For each new value x, the best subarray ending here either continues the previous run (curr + x) or starts fresh (x). Take whichever is larger. If curr was negative, carrying it forward can only hurt, so the algorithm restarts.

Step-by-step trace

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] (the example from LeetCode 53).

The answer is 6, from the subarray [4, -1, 2, 1].

Why it is correct

Kadane's algorithm is a one-dimensional dynamic program with the state compressed to a single variable. Let dp[i] be the best sum of a subarray ending at index i. Any such subarray is either nums[i] alone or a subarray ending at i - 1 plus nums[i], so dp[i] = max(nums[i], dp[i - 1] + nums[i]). The answer is the maximum of all dp[i]. Because each dp[i] needs only dp[i - 1], one variable replaces the array. If you want the broader DP picture, see our dynamic programming patterns guide.

The Python template

This is the complete solution to Maximum Subarray (LeetCode 53).

def max_subarray(nums):
    best = curr = nums[0]
    for x in nums[1:]:
        curr = max(x, curr + x)   # extend the current run, or start a new one at x
        best = max(best, curr)    # remember the best run seen so far
    return best

Initialize both variables with nums[0], not 0. Starting at 0 silently returns 0 for an all-negative array such as [-3, -1, -2], where the correct answer is -1. (Some variants allow an empty subarray with sum 0; then starting at 0 is correct. Ask which one the interviewer means.)

Returning the subarray, not just the sum

A common follow-up: "Which subarray is it?" Track where the current run started and copy it when you find a new best.

def max_subarray_with_bounds(nums):
    best = curr = nums[0]
    start = best_l = best_r = 0
    for i in range(1, len(nums)):
        if curr < 0:               # a negative run only hurts: restart at i
            curr, start = nums[i], i
        else:
            curr += nums[i]
        if curr > best:
            best, best_l, best_r = curr, start, i
    return best, best_l, best_r    # sum, first index, last index (inclusive)

Worked problem 1: Maximum Product Subarray (LeetCode 152)

Maximum Product Subarray (LeetCode 152) looks like Kadane with * instead of +, but a negative number turns the smallest product into the largest. The idea: track both the largest (hi) and smallest (lo) product ending at the current index, and swap them when x is negative. A zero resets both, because max(x, hi * x) becomes 0 and the next element starts fresh.

def max_product(nums):
    best = hi = lo = nums[0]
    for x in nums[1:]:
        if x < 0:
            hi, lo = lo, hi        # a negative number flips the largest and smallest
        hi = max(x, hi * x)
        lo = min(x, lo * x)
        best = max(best, hi)
    return best

Complexity: O(n) time, O(1) space.

Worked problem 2: Maximum Sum Circular Subarray (LeetCode 918)

In Maximum Sum Circular Subarray (LeetCode 918), the subarray may wrap from the end of the array to the start. The idea: the best subarray either does not wrap (plain Kadane for the maximum) or wraps, in which case it is the whole array minus the minimum subarray in the middle. Run Kadane for the max and the min in the same loop and take max(best_max, total - best_min).

def max_subarray_sum_circular(nums):
    total = 0
    cur_max = cur_min = 0
    best_max = best_min = nums[0]
    for x in nums:
        cur_max = max(x, cur_max + x)
        best_max = max(best_max, cur_max)
        cur_min = min(x, cur_min + x)
        best_min = min(best_min, cur_min)
        total += x
    if best_max < 0:               # every number is negative: wrapping would mean an empty subarray
        return best_max
    return max(best_max, total - best_min)

Complexity: O(n) time, O(1) space. The edge case is the whole point: if every number is negative, total - best_min equals 0, which corresponds to an empty subarray and is not allowed, so return best_max.

Worked problem 3: Best Time to Buy and Sell Stock (LeetCode 121)

Buying on day i and selling on day j earns prices[j] - prices[i], which equals the sum of the daily changes between those days. So the best single trade is the maximum subarray of the daily price changes, with an empty subarray (no trade, profit 0) allowed. That is why curr and best start at 0 here.

def max_profit(prices):
    best = curr = 0
    for i in range(1, len(prices)):
        curr = max(0, curr + prices[i] - prices[i - 1])   # Kadane on daily price changes
        best = max(best, curr)
    return best

Complexity: O(n) time, O(1) space. The more common solution tracks the minimum price so far; both are correct, and showing you can see the Kadane version is a strong signal in an interview.

Kadane's algorithm complexity and alternatives

To feel the gap between O(n²) and O(n) on 100,000 elements (LeetCode 53's upper limit on array length), try the free Big-O complexity visualizer.

Common bugs and edge cases

• Initializing best to 0 when the subarray must be non-empty. All-negative input breaks it.
• Updating best before curr. Update the run first, then compare.
• Restart condition written as curr <= 0 vs curr < 0. Both give the right sum; they only change which of two equal-sum subarrays you report. Be consistent if you return indices.
• Products: forgetting the minimum. Without lo, [-2, 3, -4] returns 3 instead of 24.
• Circular: the all-negative case. Check best_max < 0 before using total - best_min.
• Subsequence vs subarray. If elements need not be contiguous, the answer is just the sum of positives (or the largest element if none are positive). Kadane is the wrong tool.
• Test out loud: one element, all negative, all positive, zeros, and a single large negative in the middle.

Practice list: 8 Kadane problems

Problem numbers and difficulty labels were checked on LeetCode as of October 2026. Several of these appear in the Blind 75 and the NeetCode 150.

How to practice explaining it

Kadane's algorithm is short enough that interviewers judge you on the explanation: the invariant, the all-negative case, and the follow-up variants. Practice saying it out loud. CoPilot Interview's Mock Interview can mix coding questions into a practice session; it reads each question aloud and scores your spoken answer out of 10 with what to fix and a model answer. For a quick session with nothing to install, the browser mock at /ai-mock-interview has 113 questions across 9 tracks, including coding. For a one-page refresher, keep the coding interview cheat sheet open.

FAQ

What is Kadane's algorithm?

Kadane's algorithm finds the maximum sum of a contiguous subarray in one pass. For each element it decides whether to extend the current run or start a new one at that element, and it keeps the best sum seen. It runs in O(n) time and O(1) extra space.

Is Kadane's algorithm dynamic programming?

Yes. It is a one-dimensional DP where dp[i] is the best sum of a subarray ending at index i, with dp[i] = max(nums[i], dp[i-1] + nums[i]). Because each step needs only the previous value, the DP array is reduced to a single variable.

Does Kadane's algorithm work when all numbers are negative?

Yes, if you initialize both the current and best sums with the first element instead of 0. The answer is then the largest (least negative) single element. Initializing with 0 only works when an empty subarray with sum 0 is allowed.

What is the time complexity of Kadane's algorithm?

O(n) time, because it visits each element once, and O(1) extra space, because it stores only two running values. The brute-force alternative is O(n squared) and the divide-and-conquer alternative is O(n log n).

How do you modify Kadane's algorithm for the maximum product subarray?

Track both the largest and the smallest product ending at the current index. When the current number is negative, swap them before updating, because multiplying by a negative turns the smallest product into the largest. This solves LeetCode 152 in O(n) time.

How do you handle a circular array with Kadane's algorithm?

Compute the normal maximum subarray and the minimum subarray in the same pass. A wrapping subarray equals the total sum minus the minimum subarray. Return the larger of the two, unless every number is negative, in which case return the normal maximum.