Kadane's Algorithm — Maximum Subarray Sum Explained

Most people memorize Kadane's algorithm as "keep a running sum, reset when it goes negative." That description is correct but useless — it doesn't help you understand why it works, or recognize the dozen variations interviewers will throw at you.

Kadane's is a one-dimensional dynamic programming algorithm. The DP insight: at every index, you make a binary decision — either extend the current subarray, or start a new one here. That's it. Every "maximum subarray" variant reduces to this choice.

The Problem

Given an integer array (can contain negatives), find the contiguous subarray with the largest sum. Return the sum.

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6  (subarray [4, -1, 2, 1])

Brute force: check all O(n^2) subarrays, compute each sum. That's O(n^3) naively, O(n^2) with prefix sums. Kadane's does it in O(n).

The Algorithm

At each index i, you track current_max: the maximum subarray sum ending at position i. The recurrence:

current_max(i) = max(nums[i], current_max(i-1) + nums[i])

Translation: either start fresh at nums[i], or extend the previous best subarray to include nums[i]. If the previous running sum was negative, extending would only make things worse — so you start over.

Python

def max_subarray(nums):
    current_max = nums[0]
    global_max = nums[0]

for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)

return global_max

JavaScript

function maxSubarray(nums) {
  let currentMax = nums[0];
  let globalMax = nums[0];

for (let i = 1; i < nums.length; i++) {
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    globalMax = Math.max(globalMax, currentMax);
  }

return globalMax;
}

Single pass. O(n) time, O(1) space. Nothing to allocate, nothing to sort.

Why It Works — The DP Perspective

Define dp[i] = maximum subarray sum ending at index i. Then:

dp[0] = nums[0]
dp[i] = max(nums[i], dp[i-1] + nums[i])   for i > 0

The answer is max(dp[0], dp[1], ..., dp[n-1]).

Kadane's just computes this without the array — current_max is dp[i], and global_max tracks the overall maximum across all dp[i] values. Space-optimized DP.

This framing matters because it tells you exactly what variant problems look like: anything where you change the recurrence for dp[i].

Returning the Subarray Itself

Interviewers often follow up with "also return the indices." Track where the current subarray started and where the global best was found.

Python

def max_subarray_with_indices(nums):
    current_max = nums[0]
    global_max = nums[0]
    start = 0
    temp_start = 0
    end = 0

for i in range(1, len(nums)):
        if nums[i] > current_max + nums[i]:
            current_max = nums[i]
            temp_start = i
        else:
            current_max = current_max + nums[i]

if current_max > global_max:
            global_max = current_max
            start = temp_start
            end = i

return global_max, start, end

JavaScript

function maxSubarrayWithIndices(nums) {
  let currentMax = nums[0];
  let globalMax = nums[0];
  let start = 0, tempStart = 0, end = 0;

for (let i = 1; i < nums.length; i++) {
    if (nums[i] > currentMax + nums[i]) {
      currentMax = nums[i];
      tempStart = i;
    } else {
      currentMax += nums[i];
    }

if (currentMax > globalMax) {
      globalMax = currentMax;
      start = tempStart;
      end = i;
    }
  }

return [globalMax, start, end];
}

Same O(n) time, O(1) space. The key: temp_start resets whenever you start a new subarray, and only gets committed to start when that new subarray beats the global record.

Handling All-Negative Arrays

Some implementations initialize current_max = 0 and reset to 0 when it goes negative. That's buggy — if all elements are negative, they report 0 (the empty subarray). The problem typically asks for at least one element.

The correct initialization is current_max = nums[0] and starting the loop from index 1. This handles all-negative arrays correctly by returning the least negative element.

Variant: Maximum Circular Subarray

What if the array is circular — the subarray can wrap around? This shows up as LeetCode 918.

The trick: the maximum circular subarray is either:

1. A normal (non-wrapping) subarray — found by standard Kadane's


2. A wrapping subarray — which equals total_sum - minimum_subarray

Why? If you "cut out" the minimum subarray from the full array, what remains wraps around the ends and has the maximum possible sum.

def max_circular_subarray(nums):
    total = sum(nums)

# standard kadane's for max
    cur_max = glob_max = nums[0]
    # kadane's for min
    cur_min = glob_min = nums[0]

for i in range(1, len(nums)):
        cur_max = max(nums[i], cur_max + nums[i])
        glob_max = max(glob_max, cur_max)

cur_min = min(nums[i], cur_min + nums[i])
        glob_min = min(glob_min, cur_min)

# edge case: all elements negative
    if glob_max < 0:
        return glob_max

return max(glob_max, total - glob_min)

function maxCircularSubarray(nums) {
  let total = nums.reduce((a, b) => a + b, 0);
  let curMax = nums[0], globMax = nums[0];
  let curMin = nums[0], globMin = nums[0];

for (let i = 1; i < nums.length; i++) {
    curMax = Math.max(nums[i], curMax + nums[i]);
    globMax = Math.max(globMax, curMax);
    curMin = Math.min(nums[i], curMin + nums[i]);
    globMin = Math.min(globMin, curMin);
  }

if (globMax < 0) return globMax;
  return Math.max(globMax, total - globMin);
}

The all-negative edge case is critical. If every element is negative, total - glob_min would select the empty subarray (sum 0), which isn't valid. So we fall back to glob_max.

Variant: Maximum Product Subarray

Same idea, but multiply instead of add. The wrinkle: multiplying two negatives makes a positive. So you track both the maximum AND minimum product ending at each position.

def max_product_subarray(nums):
    cur_max = cur_min = result = nums[0]

for i in range(1, len(nums)):
        if nums[i] < 0:
            cur_max, cur_min = cur_min, cur_max

cur_max = max(nums[i], cur_max * nums[i])
        cur_min = min(nums[i], cur_min * nums[i])
        result = max(result, cur_max)

return result

function maxProductSubarray(nums) {
  let curMax = nums[0], curMin = nums[0], result = nums[0];

for (let i = 1; i < nums.length; i++) {
    if (nums[i] < 0) {
      [curMax, curMin] = [curMin, curMax];
    }
    curMax = Math.max(nums[i], curMax * nums[i]);
    curMin = Math.min(nums[i], curMin * nums[i]);
    result = Math.max(result, curMax);
  }

return result;
}

The swap when nums[i] < 0 is the entire insight. A negative number flips max and min. If cur_min is very negative and nums[i] is negative, their product could be the new maximum.

Complexity Analysis

Variant	Time	Space
Basic Kadane's	O(n)	O(1)
With indices	O(n)	O(1)
Circular subarray	O(n)	O(1)
Maximum product	O(n)	O(1)
Brute force (comparison)	O(n^2)	O(1)

All Kadane's variants share the same complexity profile. One pass through the array, constant extra space.

Common Interview Mistakes

Initializing to 0 instead of nums[0]. Breaks on all-negative arrays. Always start from the first element. Forgetting the circular edge case. When all elements are negative, total - min_subarray gives 0 (the empty subarray). You need a special check. Not tracking min for product variant. People try to apply sum-Kadane directly to products and wonder why [-2, 3, -4] returns 3 instead of 24. Overcomplicating the recurrence. The decision at each step is binary: extend or restart. If you're writing more than two lines inside the loop, step back.

Problem Shapes That Signal Kadane's

• "Maximum/minimum subarray sum" — direct application
• "Largest sum contiguous subarray" — same thing, different wording
• Anything asking for a contiguous segment optimizing some additive or multiplicative property
• Circular array problems where wrapping is allowed
• Stock problems like "best time to buy and sell" (single transaction variant is Kadane's in disguise — prices[i] - prices[i-1] transforms it into maximum subarray)

The common thread: you're looking for the best contiguous segment, and the "extend or restart" decision makes sense for the metric you're optimizing.

Practice these patterns on CodeUp — start with basic Kadane's, then work through the variants until the recurrence feels automatic.