Kadane's algorithm is a problem solving technique used to solve the Maximum Subarray Problem in linear time.

What's the maximum subarray problem?

You are given an array and you need to find the subarray with the maximum sum.

A subarray is a contiguous sequence of elements within the array.

If the array contains only positive numbers, the answer is the entire array, since adding more positive numbers always increases the sum.

The problem becomes harder when the array contains negative numbers, since we need to decide which elements to include and which to skip.

For example, in the array:

the subarray with the maximum sum is [4, -1, 2, 1], with a total sum of 6.

Brute Force Approach

The brute force approach to solve this problem is simple.

The naive triple-loop version (try every start, every end, sum each subarray) runs in O(n³). With a running-sum optimization that incrementally updates the sum as you extend the subarray, it drops to O(n²). Kadane's algorithm improves this further to O(n).

Kadane's Algorithm

Kadane's Algorithm runs in O(n) time. At each element, it decides whether to:

At each element, compare currentSum + nums[i] against nums[i] alone, and take the larger. Equivalently: if the running sum is negative, discard it and start a new subarray with nums[i], because any subarray that includes a negative prefix can be improved by dropping the prefix.

This keeps the running sum as large as possible.

The rule simplifies to: if the running sum is negative, restart at the current element; otherwise extend.

Both cases are unified by currentSum = max(currentSum + nums[i], nums[i]).

Here's how Kadane's Algorithm looks in code:

Initialize both currentSum and maxSum to nums[0], not to 0. If you start with maxSum = 0, an all-negative array like [-3, -1, -2] will incorrectly return 0 instead of -1. The convention that "the empty subarray has sum 0" is not what Kadane's classic formulation expects, the answer must be a non-empty contiguous subarray.

Let's run Kadane's algorithm on the array from earlier: [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Start with currentSum = -2 and maxSum = -2 (both initialized to nums[0]). Then iterate from index 1 onward.

The final answer is 6, which corresponds to the subarray [4, -1, 2, 1] from indices 3 through 6.

Watch the resets. At index 1, currentSum becomes 1 alone instead of -2 + 1 = -1, because the previous prefix -2 was negative and dragging the sum down. At index 3, the same thing happens: currentSum becomes 4 alone instead of -2 + 4 = 2. These are the moments where "discard the negative prefix" pays off, and they're what make Kadane's algorithm work.

Kadane's algorithm is often presented as a clever trick, but it's really a one-liner of dynamic programming. Reframing it as DP makes the recurrence obvious and shows where the algorithm comes from.

Define dp[i] = the maximum sum of a contiguous subarray ending at index i.

The recurrence is:

At each index, we have two choices: extend the best subarray ending at i-1 by appending nums[i], or start fresh at i with just nums[i] alone. We take whichever is larger.

The final answer is max(dp[0], dp[1], ..., dp[n-1]), the largest value over all possible ending indices.

This is exactly Kadane's algorithm:

Since dp[i] depends only on dp[i-1], we don't need to store the full dp array. One variable is enough. That's the space optimization built into Kadane's algorithm.

The DP framing also makes the all-negative-array case obvious. dp[i] is the best subarray ending at i. For an all-negative array, any subarray of length greater than one has a smaller sum than its largest element, since adding more negative numbers only decreases the sum. So dp[i] = nums[i] for every i, and the answer is the largest single element. This is why we initialize maxSum = nums[0] rather than 0.

Once you understand the core Kadane recurrence, several common follow-up problems become straightforward.

Return the actual subarray, not just the sum

Track start and end indices alongside currentSum. Whenever currentSum resets to nums[i] alone (that is, when nums[i] > currentSum + nums[i]), update start = i. Whenever currentSum exceeds maxSum, save the current window as the best so far by setting maxStart = start and maxEnd = i. At the end, the answer is the subarray from maxStart to maxEnd.

Maximum Product Subarray

Multiplication has a sign-flip problem. Multiplying by a negative number turns the smallest product into the largest, and vice versa, so tracking only the running maximum loses information. The fix is to track BOTH currentMin and currentMax at each index. At each step:

The global answer is the running maximum of currentMax.

Maximum Sum Circular Subarray

The array is circular: the last element connects back to the first. There are two cases. Either the maximum subarray is non-circular, in which case standard Kadane gives the answer. Or it wraps around the end and back to the beginning, in which case the elements NOT included form a contiguous subarray in the middle with the minimum sum. The wrap-around answer is totalSum - minSubarraySum.

The final answer is the max of the two cases. The edge case: if all elements are negative, the minimum subarray covers the whole array, and totalSum - minSubarraySum = 0, which would correspond to an empty subarray. Since the problem requires a non-empty subarray, return the standard Kadane result in that case.

Maximum Sum Rectangle in 2D Matrix

Reduce the 2D problem to 1D. For each pair of rows (r1, r2), collapse the matrix between those rows into a 1D array by summing each column from row r1 to row r2. Then apply Kadane on the 1D array to find the best column range. Try all O(rows^2) row pairs, each taking O(cols) for the Kadane pass, giving total complexity O(rows^2 * cols).