Kadane's Algorithm — Maximum Subarray and Beyond

The Maximum Subarray problem asks: given an integer array, find the contiguous subarray with the largest sum. A brute-force approach would enumerate all subarrays in O(n²) or O(n³). Kadane's Algorithm solves it in O(n) time and O(1) space with a single pass. That dramatic improvement comes from one DP insight hiding in plain sight: a subarray ending at index i is only worth extending if the sum up to i-1 is positive.

Kadane's Algorithm achieves O(n) time and O(1) space for the Maximum Subarray problem — the same result as a brute-force O(n³) approach but 100x faster, achieved through a single DP insight: a subarray ending here is only worth extending if its sum is positive. Understanding why this is true, not just how to code it, is what separates candidates who can apply Kadane's to novel variants from those who can only solve the textbook problem.

This guide explains the algorithm from first principles, provides a clean Python implementation, traces the execution step by step, and maps the pattern to four LeetCode problems — including some that require non-obvious extensions of the core idea. It also clarifies the persistent confusion between Kadane's Algorithm and the sliding window technique.

Joseph Kadane developed this algorithm in 1984 at Carnegie Mellon University in response to a challenge to find the most efficient solution to the maximum subarray problem. The problem had been posed by Ulf Grenander, who wanted an efficient algorithm for digital image analysis. Kadane's insight — presented during a collaborative session — reduced the time complexity from O(n²) to O(n) in a single elegant observation.

Formally, the algorithm maintains two variables: current_sum (the maximum subarray sum ending at the current index) and max_sum (the global maximum seen so far). At each index i, it makes a binary decision: either extend the subarray that ended at i-1 (taking current_sum + nums[i]) or start a fresh subarray at i (taking nums[i] alone). It always chooses the larger of the two. The global max_sum is updated whenever current_sum exceeds it.

This makes Kadane's Algorithm simultaneously an instance of greedy thinking (make the locally optimal choice at each step) and dynamic programming (the choice at each step depends on the optimal solution to the subproblem ending at the previous index). Most algorithm textbooks classify it as DP; the greedy framing helps with intuition.

Consider the canonical example: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. We initialize current_sum = nums[0] = -2 and max_sum = -2. At index 1, nums[1] = 1. We choose max(-2 + 1, 1) = max(-1, 1) = 1. current_sum = 1, max_sum = 1. At index 2, nums[2] = -3. We choose max(1 + (-3), -3) = max(-2, -3) = -2. current_sum = -2, max_sum = 1.

At index 3, nums[3] = 4. We choose max(-2 + 4, 4) = max(2, 4) = 4. current_sum = 4, max_sum = 4. Notice the algorithm restarted here — the previous subarray sum was negative, so it is better to begin fresh. At index 4, nums[4] = -1: current_sum = max(4 + (-1), -1) = 3. At index 5, nums[5] = 2: current_sum = max(3 + 2, 2) = 5, max_sum = 5. At index 6, nums[6] = 1: current_sum = 6, max_sum = 6. At index 7, nums[7] = -5: current_sum = 1. At index 8, nums[8] = 4: current_sum = 5, max_sum = 6.

The algorithm correctly identifies the maximum subarray [4, -1, 2, 1] with sum 6. The recurrence that drives this is dp[i] = max(nums[i], dp[i-1] + nums[i]). Notice that dp[i-1] + nums[i] represents extending the previous subarray, and nums[i] alone represents starting fresh. The fresh start wins whenever dp[i-1] is negative — a negative prefix only drags the sum down.

The core implementation of Kadane's Algorithm in Python is concise: initialize current_sum and max_sum to nums[0], then iterate from index 1 to n-1, updating current_sum = max(nums[i], current_sum + nums[i]) and max_sum = max(max_sum, current_sum). Return max_sum. This is five lines of logic and handles all-negative arrays correctly because we initialize to nums[0] rather than 0.

A common extension is tracking the actual subarray indices, not just the sum. This requires maintaining start, end, and temp_start variables: when current_sum resets to nums[i] (the fresh-start branch wins), update temp_start = i. When max_sum is updated, set start = temp_start and end = i. After the loop, the maximum subarray is nums[start:end+1].

For the LeetCode 53 (Maximum Subarray) submission, the five-line version without index tracking is sufficient and runs in O(n) time, O(1) space. In Python, this looks like: current = max_s = nums[0]; for n in nums[1:]: current = max(n, current + n); max_s = max(max_s, current); return max_s.

LeetCode 53 (Maximum Subarray) is the direct application — Kadane's is the intended O(n) solution. The divide-and-conquer solution also works in O(n log n) but is slower and harder to implement. In interviews, demonstrating Kadane's Algorithm immediately signals familiarity with DP patterns.

LeetCode 152 (Maximum Product Subarray) extends the pattern by requiring both a max and min running product, because a large negative times a large negative becomes a large positive. Instead of one current variable, you maintain current_max and current_min and update both at each step: new_max = max(nums[i], current_max * nums[i], current_min * nums[i]). This is Kadane's Algorithm generalized from addition to multiplication.

LeetCode 918 (Maximum Sum Circular Subarray) extends Kadane's to a circular array. The answer is either the standard maximum subarray (use Kadane's directly) or the total sum minus the minimum subarray (which covers the wraparound case). This requires running both Kadane's maximum subarray and a modified Kadane's minimum subarray in a single pass.

LeetCode 121 (Best Time to Buy and Sell Stock) is structurally Kadane's Algorithm in disguise. If you convert prices to daily gains (gains[i] = prices[i] - prices[i-1]), the maximum profit is exactly the maximum subarray sum of the gains array — which Kadane's solves directly. Understanding this connection reveals a deep structural similarity between greedy and DP approaches.

Kadane's Algorithm and the sliding window technique are often confused because both scan an array in a single pass and maintain a running sum. The critical difference is in how the window boundary resets. Sliding window maintains a valid window by shrinking from the left when a constraint is violated; Kadane's discards the entire prefix and restarts when the running sum goes negative. In sliding window, the window always has a meaningful left boundary; in Kadane's, 'start fresh' means the new subarray begins at the current index.

When are they equivalent? For the specific case of Maximum Subarray with non-negative numbers only, both produce the same behavior — the window never needs to reset. For general arrays with negative numbers, only Kadane's (the DP approach) gives the correct O(n) answer. Sliding window requires a constraint that defines a valid window (e.g., sum ≤ k, at most k distinct characters); Kadane's has no such external constraint — the only criterion is maximizing the sum.

The practical rule: use sliding window when the problem gives you a constraint that defines valid windows (fixed size, bounded sum, at-most-k condition). Use Kadane's when the problem asks for a maximum subarray sum or a variant thereof — the constraint is entirely internal to the sum itself. These two patterns are complementary, not interchangeable.

The most frequent mistake is initializing max_sum = 0 instead of max_sum = nums[0]. With zero initialization, an all-negative input like [-3, -1, -2] returns 0, which is wrong — the correct answer is -1 (the least-negative element). Initializing to nums[0] and starting the loop at index 1 handles all-negative arrays correctly because the loop will always prefer the least-negative element over the negative running sum.

A second common mistake is using max_sum = float('-inf') but starting the iteration at index 0 without initializing current_sum correctly. When current_sum is initialized to 0 instead of nums[0], and the first element is negative, current_sum resets to the first element on the first iteration only if the max(nums[i], current_sum + nums[i]) branch is taken — which requires nums[i] > current_sum + nums[i], i.e., 0 > current_sum. This works mathematically but is an unnecessary source of confusion; the explicit nums[0] initialization is cleaner.

Empty array inputs require a guard at the start. LeetCode 53 guarantees a non-empty array, but production code should handle empty input. For very large arrays, Python handles arbitrarily large integers natively, but in Java or C++ you should be aware that summing 10^5 elements of value 10^4 approaches 10^9, which fits in a 32-bit int — but edge cases near INT_MAX can overflow if you use int instead of long.

Kadane's Algorithm is the most beginner-friendly dynamic programming algorithm precisely because its DP table collapses to a single variable. The recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) is short enough to memorize but deep enough to teach the core DP principle: at each step, ask whether the optimal solution to the previous subproblem helps or hurts the current step.

Once you internalize Kadane's, you have a template for a family of problems: maximum product subarray (extend with max/min tracking), circular maximum subarray (combine max and min Kadane passes), and stock profit problems (reframe as subarray sum on daily differences). Each variant requires understanding why the core recurrence works, not just how to code it.

The pattern extends beyond arrays too. Maximum path sum in a binary tree (LeetCode 124) uses a similar DP framing: at each node, decide whether to include the path through the left child, the right child, both, or neither. The same 'extend vs. restart' logic applies in a tree structure instead of a linear array.

Drill Maximum Subarray (LeetCode 53), Maximum Product Subarray (LeetCode 152), and Maximum Sum Circular Subarray (LeetCode 918) together as a progression. Each one builds on the previous and deepens your understanding of the underlying DP principle. YeetCode's spaced repetition system tracks all three together so you review them at optimal intervals and retain the pattern through your entire job search.