Maximum Subarray LeetCode Solution: Kadane's Algorithm Explained

Maximum Subarray (#53) is one of the most iconic problems in all of computer science. It appears on nearly every curated interview list, and for good reason — it introduces Kadane's algorithm, an elegant O(n) technique that every serious candidate needs to know cold.

The problem is deceptively simple: given an integer array, find the contiguous subarray with the largest sum. Yet it opens the door to an entire family of problems built on the same greedy/DP insight. If you understand Maximum Subarray deeply, you unlock Maximum Product Subarray (#152), Maximum Circular Subarray (#918), and even Best Time to Buy and Sell Stock (#121).

In this walkthrough, you will move from brute force to Kadane's algorithm step by step. By the end, the one-line core of Kadane's will feel as natural as breathing.

You are given an integer array nums. Your job is to find the contiguous subarray (containing at least one element) that has the largest sum, and return that sum. The keyword here is contiguous — you cannot skip elements or rearrange them.

For example, given [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is 6, coming from the subarray [4, -1, 2, 1]. Notice that including the -1 between 4 and 2 is still worth it because the overall sum stays positive and grows.

The constraint that at least one element must be included matters when all elements are negative. In that case, the answer is simply the least negative number — you cannot return 0 by choosing an empty subarray.

The most intuitive approach is to check every possible subarray and track the maximum sum. You can enumerate all starting indices i and ending indices j, then sum nums[i..j]. This gives O(n^3) time with the naive triple loop, or O(n^2) if you maintain a running sum as you extend j.

While the O(n^2) brute force is correct and easy to implement, it fails on large inputs. With arrays up to 100,000 elements, you need something fundamentally faster. This is where Kadane's algorithm enters — dropping the complexity all the way down to O(n).

The brute force is still useful in interviews as a starting point. State it clearly, mention its time complexity, and then transition to the optimal approach. Interviewers want to see that you can recognize when brute force is insufficient and know the path to improvement.

Kadane's algorithm solves maximum subarray in a single pass. You maintain two variables: currentSum (the best sum ending at the current position) and maxSum (the global best). At each element, you make one decision: is it better to extend the previous subarray by adding this element, or start a brand new subarray beginning here?

That decision is captured in one line: currentSum = Math.max(nums[i], currentSum + nums[i]). If currentSum + nums[i] is greater than nums[i] alone, you extend. Otherwise, you restart. After updating currentSum, you compare it against maxSum and keep the larger value.

Here is the complete logic. Initialize currentSum and maxSum both to nums[0]. Then iterate from index 1 to the end. At each step: currentSum = max(nums[i], currentSum + nums[i]), then maxSum = max(maxSum, currentSum). When the loop finishes, maxSum holds your answer.

The time complexity is O(n) because you touch each element exactly once. The space complexity is O(1) because you only store two variables. This makes Kadane's algorithm one of the most efficient solutions in all of LeetCode.

Kadane's algorithm can be understood through two lenses. From the greedy perspective, if the running sum becomes negative, there is no benefit to carrying it forward. Starting fresh from the current element is always better than dragging a negative prefix along. This greedy choice at every step leads to the globally optimal answer.

From the dynamic programming perspective, define dp[i] as the maximum subarray sum ending at index i. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]). Each element either starts a new subarray or extends the previous best. The answer is max(dp[0], dp[1], ..., dp[n-1]). Kadane's algorithm is simply this DP with O(1) space — you only ever need dp[i-1] to compute dp[i].

This dual interpretation is what makes the problem such a powerful teaching tool. It bridges greedy reasoning and dynamic programming, showing that the two frameworks can lead to identical solutions. Understanding both perspectives deepens your intuition for other problems that blend greedy and DP thinking.

The most critical edge case is an array of all negative numbers. Because you must include at least one element, the answer is the maximum (least negative) value. Kadane's algorithm handles this naturally — currentSum will reset to each element individually, and maxSum will track the largest among them.

A single-element array is trivially handled: the answer is that one element. Arrays with all positive numbers return the total sum, since the best subarray is the entire array.

Once you master the basic Maximum Subarray, several important variations await. Maximum Product Subarray (#152) requires tracking both the running maximum and running minimum because a negative times a negative flips the sign. Maximum Sum Circular Subarray (#918) adds the wrinkle of wrap-around, which you solve by also computing the minimum subarray and subtracting it from the total sum.

Maximum Subarray (#53) is more than just one problem — it is a gateway to an entire class of "running sum" and "extend or restart" problems. The core decision at each step — should I keep building on what I have, or cut my losses and start over? — appears everywhere in algorithm design.

Best Time to Buy and Sell Stock (#121) is essentially maximum subarray on the daily price differences. Longest Turbulent Subarray (#978) uses the same extend-or-restart logic with alternating comparisons. Even some interval and sliding window problems echo the same structural pattern.

The best way to internalize Kadane's algorithm is active recall. Solve Maximum Subarray from scratch, then immediately try Maximum Product Subarray (#152) and Maximum Circular Subarray (#918). Use YeetCode flashcards to drill the pattern until the one-line recurrence is second nature. When you see a contiguous subarray optimization problem in an interview, Kadane's should be the first tool you reach for.