Kadane's Algorithm Explained: Maximum Subarray and Its Variations

You face a maximum subarray question in a coding round, and your first instinct is to check every possible start and end index with two nested loops that run in O(n^2) time. That brute force approach fails when the input size n reaches 10^5 because the compiler throws a time limit exceeded error, which means you need Kadane's algorithm to compute the answer in a single pass of O(n) time and O(1) space.

The Core Mechanism of Kadane's Algorithm

You maintain two integer variables as you iterate through the array: current_sum and max_sum. At each element, you decide whether to extend the existing subarray by adding the current number or to abandon the past and start a fresh subarray right at this element.

For the input array [-2, 1, -3, 4, -1, 2, 1, -5, 4], you initialize both variables to the first element -2. When you move to index 1 with value 1, your current_sum becomes the maximum of 1 and -2 + 1, which evaluates to 1. Your max_sum updates to 1.

When you reach index 3 with value 4, your current_sum compares extending the previous sum of -2 with starting fresh at 4. Starting fresh wins because 4 is larger than -2 + (-3) + 4.

The All-Negative Trap

If your input array consists entirely of negative numbers like [-5, -2, -3, -4], standard implementations that initialize current_sum and max_sum to 0 will incorrectly return 0 as the maximum sum. An empty subarray is not a valid answer when the problem demands at least one element.

You must initialize max_sum and current_sum to the very first element of the array, which is -5, rather than 0. This forces the algorithm to pick the single least negative element instead of returning a zero-sum empty slice.

Maximum Product Subarray

Switching from sum to product introduces a complication because multiplying two negative numbers turns them positive. You cannot discard a very small negative number when a future negative multiplier might appear.

You maintain both max_so_far and min_so_far at each step of the array traversal. When you encounter a negative number like -2 at index 2 in [2, 3, -2, 4], you swap your current maximum and minimum trackers before multiplying. This ensures that the old minimum, which was negative, scales up into a large positive product when multiplied by another negative value.

Maximum Circular Subarray

A circular array allows the subarray to wrap around from the last element back to the first. The maximum circular sum is either the standard linear maximum sum or the total sum of the array minus the minimum subarray sum.

Consider the array [5, -3, 5]. The standard maximum linear sum is 5 from a single element. The total sum is 7, and the minimum subarray sum is -3. Subtracting that minimum from the total sum gives 7 - (-3), which equals 10, representing the wrap-around subarray [5, 5]. You must handle the edge case where every element is negative; in that specific scenario, the minimum sum equals the total sum, so you fall back entirely to the standard linear maximum sum.

Maximum Sum with One Deletion

Allowing a single deletion changes your state machine into two parallel trackers at every index i. You track max_ending_here, which is the maximum sum ending at i with zero deletions, and max_ending_here_with_one_deletion, which is the maximum sum ending at i with exactly one deletion used so far.

For the array [1, -2, 0, 3], when you reach -2, you can either delete -2 by carrying over the sum from the element before -2, or you can keep -2 and delete some earlier element. You take the maximum of these two choices at every step, which gives you the optimal path through the array without resorting to an O(n^2) search.

Screenshot this rule of thumb for your next interview:

• Initialize sum variables to the first array element, never zero.
• Track both maximum and minimum for products or deletions.
• For circular arrays, compare standard linear sum against total sum minus minimum sum.
• Run one pass and update state variables in constant time.

Open DSA Tracker and submit a solution for the maximum subarray problem using O(n) time right now.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Sorting algorithms on Wikipedia.