Kadane's Algorithm: Maximum Subarray Sum and Every Variant Interviewers Ask

Maximum Subarray (LeetCode 53) is one of the most frequently asked array problems in Indian interviews, from campus OAs to FAANG phone screens. The base solution is three lines, which is exactly why interviewers rarely stop there: they follow up with "return the indices", "what if it is circular?", "what about products?", or "now do it on a matrix". This guide gives you the base algorithm with a proof you can say out loud, then every common variant, each with code that has been checked against brute force on thousands of random arrays.

The Maximum Subarray Problem

Given an integer array, find the contiguous, non-empty subarray with the largest sum. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6, from [4, -1, 2, 1].

The prefix-sum view is worth noticing: maximising P[j] - P[i-1] is the same problem as Best Time to Buy and Sell Stock (buy at the minimum prefix, sell at the current one). Kadane and "min so far" are two faces of one idea; the prefix sum guide explores the other face.

Kadane's Intuition: Never Carry a Negative Prefix

Walk left to right and ask, at every index i: what is the best subarray that ends exactly here? There are only two candidates:

• The element alone: nums[i].
• The best subarray ending at i - 1, extended by nums[i].

The second is better exactly when the previous best is positive. So whenever the running sum goes negative, it is dead weight: any subarray that included it would be better off starting later. That is the whole algorithm. The global answer is the best of these "ending here" values over all i, because the optimal subarray has to end somewhere.

Kadane's Algorithm Code and Dry Run

long long maxSubArray(const vector<int>& nums) {
    long long best = nums[0], cur = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        cur = max<long long>(nums[i], cur + nums[i]);   // extend or restart
        best = max(best, cur);
    }
    return best;
}

public static int maxSubArray(int[] nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

Dry run on [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Answer 6. For an all-negative array like [-3, -1, -2] the same code returns -1, the largest single element, because max(x, cur + x) always prefers a lone negative over adding another negative.

Why Kadane's Algorithm Is Correct

Define E[i] = maximum sum of a non-empty subarray that ends at index i. Claim: E[i] = max(nums[i], E[i-1] + nums[i]).

Proof. Any subarray ending at i is either [i..i], with sum nums[i], or [j..i] for some j < i, whose sum is sum(j..i-1) + nums[i]. The largest possible sum(j..i-1) over all j is by definition E[i-1]. So the best of the second kind is E[i-1] + nums[i], and E[i] is the max of the two kinds. The base case E[0] = nums[0] is trivial, so by induction every E[i] is computed correctly.

The optimal subarray overall ends at some index k, so its sum is E[k], and max over i of E[i] is the answer. Since E[i] only depends on E[i-1], one variable suffices: that is the space optimisation from O(n) to O(1).

Saying "dp[i] is the best subarray ending at i; it either extends dp[i-1] or starts fresh" in an interview is the proof they want. It also explains why this counts as dynamic programming rather than a lucky greedy trick, which is a common follow-up question.

Returning the Subarray, Not Just the Sum

Track where the current run started. When you restart at i, the candidate start becomes i; when the current sum beats the best, record the candidate start and i as the best range.

def max_subarray_with_indices(nums):
    best, best_l, best_r = nums[0], 0, 0
    cur, cur_l = nums[0], 0
    for i in range(1, len(nums)):
        if cur < 0:                 # restarting is strictly better
            cur, cur_l = nums[i], i
        else:
            cur += nums[i]
        if cur > best:
            best, best_l, best_r = cur, cur_l, i
    return best, best_l, best_r     # (6, 3, 6) for the example

Ties: this version keeps the earliest best subarray and, because it extends when cur == 0, prefers longer runs over restarting. If the interviewer wants the shortest or the latest among equal sums, adjust the < and > to <= and >= accordingly and say which rule you chose.

Maximum Sum Circular Subarray (LeetCode 918)

Now the array wraps: a subarray may run off the end and continue from the start. The optimal subarray is one of two shapes:

1. No wrap. A normal subarray: plain Kadane gives it.
2. Wraps around. It covers a suffix and a prefix, so what it leaves out is a contiguous middle block. Maximising what you keep is the same as minimising what you leave out: answer = total - (minimum subarray sum).

int maxSubarraySumCircular(const vector<int>& nums) {
    int total = 0, curMax = 0, curMin = 0;
    int bestMax = nums[0], bestMin = nums[0];
    for (int x : nums) {
        curMax = max(x, curMax + x);
        bestMax = max(bestMax, curMax);
        curMin = min(x, curMin + x);
        bestMin = min(bestMin, curMin);
        total += x;
    }
    // all negative: the "wrap" would be the empty subarray, which is not allowed
    return bestMax < 0 ? bestMax : max(bestMax, total - bestMin);
}

def max_subarray_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:
        return best_max
    return max(best_max, total - best_min)

Examples: [5, -3, 5]: no-wrap best is 7 (whole array), min subarray is -3, total 7, wrap gives 10 from [5, 5] across the boundary. Answer 10. [-3, -2, -3]: bestMax = -2 is negative, so return -2. Without that guard, total - bestMin = -8 - (-8) = 0, an empty subarray, which is the classic bug.

An alternative solution uses prefix sums with a monotonic deque over a doubled array (window length at most n), which generalises to "circular with a maximum length" but costs O(n) extra space. The two-Kadane trick is what interviewers expect.

Maximum Product Subarray (LeetCode 152)

Products break plain Kadane because a negative number flips order: the most negative product so far becomes the largest after multiplying by a negative. So track both the maximum and minimum product ending at each index.

int maxProduct(const vector<int>& nums) {
    int best = nums[0], hi = nums[0], lo = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        int x = nums[i];
        if (x < 0) swap(hi, lo);   // a negative turns the min into the max
        hi = max(x, hi * x);
        lo = min(x, lo * x);
        best = max(best, hi);
    }
    return best;
}

def max_product(nums):
    best = hi = lo = nums[0]
    for x in nums[1:]:
        if x < 0:
            hi, lo = lo, hi
        hi = max(x, hi * x)
        lo = min(x, lo * x)
        best = max(best, hi)
    return best

Dry run on [-2, 3, -4]: start hi = lo = -2. At 3: hi = max(3, -6) = 3, lo = min(3, -6) = -6. At -4: swap gives hi = -6, lo = 3; then hi = max(-4, 24) = 24, lo = min(-4, -12) = -12. Answer 24, the whole array. Zeros reset both trackers automatically, since max(0, ...) and min(0, ...) restart at 0. There is also a neat two-pass alternative (maximum of running prefix and suffix products, resetting at zero) covered in the dedicated maximum product subarray post.

Variants: One Deletion, Absolute Sum and Stock Profit

Maximum Subarray Sum with One Deletion (LeetCode 1186)

You may delete at most one element (the result must stay non-empty). Keep two states ending at i: keep = best sum with no deletion (plain Kadane), and deleted = best sum with exactly one deletion used. Either the deletion happened earlier and we extend (deleted + x), or we delete x itself and take the previous keep.

def maximum_sum_one_deletion(arr):
    keep = arr[0]
    deleted = float('-inf')        # cannot delete the only element at i = 0
    best = arr[0]
    for x in arr[1:]:
        deleted = max(deleted + x, keep)   # uses OLD keep: delete x
        keep = max(keep + x, x)
        best = max(best, keep, deleted)
    return best

[1, -2, 0, 3] gives 4 (delete -2), [1, -2, -2, 3] gives 3, and [-1, -1, -1, -1] gives -1. This "Kadane with a small state machine" generalises: at most k deletions means k + 1 states.

Maximum Absolute Sum of Any Subarray (LeetCode 1749)

Run max-Kadane and min-Kadane together and return max(best, -worst). Allowing empty subarrays (reset to 0) is fine here since the answer is at least 0.

def max_absolute_sum(nums):
    hi = lo = best = 0
    for x in nums:
        hi = max(0, hi + x)
        lo = min(0, lo + x)
        best = max(best, hi, -lo)
    return best        # 5 for [1,-3,2,3,-4], 8 for [2,-5,1,-4,3,-2]

Best Time to Buy and Sell Stock (LeetCode 121) as Kadane

Profit from buying on day i and selling on day j is the sum of daily changes prices[k] - prices[k-1] for k in (i, j]. So the maximum profit is the maximum subarray of the difference array, floored at 0. For [7, 1, 5, 3, 6, 4] the differences are [-6, 4, -2, 3, -2], whose best subarray is 4 - 2 + 3 = 5. Seeing this equivalence is a nice moment in an interview.

2D Kadane: Maximum Sum Rectangle in a Matrix

Find the sub-rectangle with the largest sum. Brute force over all rectangles with 2D prefix sums is O(R² · C²). The trick: fix a top row and a bottom row. Collapse every column between them into one number (its sum over those rows); now the best rectangle with those vertical bounds is just the maximum subarray of that 1-D array.

def max_sum_rectangle(matrix):
    rows, cols = len(matrix), len(matrix[0])
    best = float('-inf')
    for top in range(rows):
        col_sum = [0] * cols
        for bottom in range(top, rows):
            for c in range(cols):
                col_sum[c] += matrix[bottom][c]     # extend band by one row
            best = max(best, max_subarray(col_sum))
    return best

Complexity: O(R²) bands, each updated in O(C) and scanned by Kadane in O(C), total O(R² · C). If R > C, transpose first so the squared term is the smaller dimension. On the classic textbook matrix [[1,2,-1,-4,-20],[-8,-3,4,2,1],[3,8,10,1,3],[-4,-1,1,7,-6]] the answer is 29 (rows 1 to 3, columns 1 to 3).

The harder follow-up, Max Sum of Rectangle No Larger Than K (LeetCode 363), keeps the same band idea but replaces Kadane with "best subarray sum ≤ k", solved with prefix sums and a sorted set (lower_bound(prefix - k)), for O(R² · C log C). More grid techniques are in the matrix and grid problems guide.

The Divide and Conquer Follow-Up

LeetCode 53's statement literally suggests trying divide and conquer, and some interviewers ask for it to test recursion. The best subarray lies entirely in the left half, entirely in the right half, or crosses the midpoint. The crossing case is the best suffix of the left half plus the best prefix of the right half, computed in linear time.

def max_subarray_dc(nums):
    def solve(lo, hi):
        if lo == hi:
            return nums[lo]
        mid = (lo + hi) // 2
        best_left_suffix, s = float('-inf'), 0
        for i in range(mid, lo - 1, -1):
            s += nums[i]
            best_left_suffix = max(best_left_suffix, s)
        best_right_prefix, s = float('-inf'), 0
        for i in range(mid + 1, hi + 1):
            s += nums[i]
            best_right_prefix = max(best_right_prefix, s)
        cross = best_left_suffix + best_right_prefix
        return max(solve(lo, mid), solve(mid + 1, hi), cross)
    return solve(0, len(nums) - 1)

T(n) = 2T(n/2) + O(n) = O(n log n). It is slower than Kadane, so why care? Returning four values per segment (total, best prefix, best suffix, best overall) makes it O(n) and, more importantly, turns it into a segment tree node that answers "maximum subarray in range [l, r]" with point updates in O(log n). That is the real-world reason to know it; see segment trees.

How Kadane Shows Up in Interviews

Because the base problem is well known, interviewers mostly use it to test depth. A typical progression:

Red flags: using a sliding window (it does not work, because with negatives there is no monotonic condition to shrink on), returning 0 for all-negative input, or being unable to say why dropping a negative prefix is safe. Strong signals: naming the DP state, connecting it to Best Time to Buy and Sell Stock, and testing on an all-negative array before the interviewer does.

Common Kadane Mistakes

• Initialising best to 0 when subarrays must be non-empty.
• Circular without the all-negative guard, returning 0.
• Max product without tracking the minimum, failing on [-2, 3, -4].
• Swapping after updating in max product: the swap must happen before computing new hi and lo.
• Using the new keep in one-deletion when computing deleted; the order of updates matters.
• Overflow: with n = 10⁵ and values up to 10⁹, sums exceed 32-bit. Use 64-bit accumulators when constraints are large (LeetCode 53's bounds fit in int, but OAs vary).
• Subarray vs subsequence: if non-contiguous elements are allowed, the answer is just the sum of positives (or the max element if none), no Kadane needed.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.