Maximum Subarray LeetCode 53 Deep Dive

LeetCode 53 — Maximum Subarray — gives you an integer array nums that may contain negative numbers, and asks you to find the contiguous subarray with the largest sum and return that sum. For example, given nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is 6, achieved by the subarray [4, -1, 2, 1]. Unlike problems that restrict to non-negative inputs, the presence of negative numbers means you cannot simply sum the entire array — you must identify which contiguous slice maximizes the total.

The problem is rated Medium on LeetCode and is one of the most frequently cited examples of dynamic programming made elegant through state compression. The brute force checks all O(n^2) subarrays and their sums in O(n^3) or O(n^2) time, but the optimal solution runs in O(n) time and O(1) space using a technique known as Kadane's algorithm. The follow-up asks for an O(n log n) divide-and-conquer solution, which is less efficient but demonstrates a powerful algorithmic technique.

Understanding this problem deeply pays dividends across the LeetCode canon: it is mathematically equivalent to Best Time to Buy and Sell Stock (LeetCode 121), it is the foundation of Kadane's algorithm family, and its divide-and-conquer solution illustrates the crossing-subarray pattern that appears in merge sort-style problems. Every serious LeetCode practitioner should have both the Kadane's and divide-and-conquer solutions memorized.

Kadane's algorithm maintains two variables: currentSum (the best subarray sum ending at the current index) and maxSum (the best subarray sum seen anywhere so far). At each element, you make a single decision: should the subarray ending here extend the previous subarray (currentSum + num), or should it start fresh at the current element (num)? You pick whichever is larger: currentSum = max(num, currentSum + num). Then update maxSum = max(maxSum, currentSum).

Initialize currentSum = nums[0] and maxSum = nums[0] (not 0) before the loop starts from index 1. This correctly handles the case where all elements are negative — the answer is the least negative single element, not 0. After the loop, maxSum holds the answer. For nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]: starting from -2, the algorithm traces currentSum through [-2, 1, -2, 4, 3, 5, 6, 1, 5] and maxSum peaks at 6, which is correct.

The time complexity is O(n) — one pass through the array. The space complexity is O(1) — only two variables regardless of input size. This makes Kadane's algorithm one of the most space-efficient dynamic programming solutions: it reduces what could be an O(n) DP table to two rolling scalars.

The correctness of Kadane's algorithm rests on one key observation: at each index i, the maximum subarray sum ending exactly at i is either nums[i] alone (start a new subarray) or nums[i] plus the maximum subarray sum ending at i-1 (extend). If the best subarray ending at i-1 has a negative sum, extending it would only hurt — it is better to discard it and start fresh. If it has a non-negative sum, extending always helps or is neutral.

This decision — extend or restart — is locally optimal and globally optimal. The global maximum subarray must end somewhere. At whatever index it ends, the best subarray ending there is captured by currentSum. By taking the maximum of currentSum over all indices, maxSum accumulates the global answer. No dynamic programming table is needed because the future optimal choice at index i+1 only depends on currentSum at index i, not on any earlier values.

A common mental model: think of currentSum as a running tally. If the tally goes negative, throw it out and start counting from the next element. The tally is never reset to 0 explicitly — instead, the max(num, currentSum + num) choice handles it implicitly: if currentSum + num < num, that means currentSum < 0, and you naturally restart.

The divide-and-conquer approach splits the array in half at the midpoint. The maximum subarray is then in exactly one of three places: entirely in the left half, entirely in the right half, or crossing the midpoint (starting somewhere in the left half and ending somewhere in the right half). Recursively solve the left and right halves. The crossing subarray is computed in O(n) per level by extending left from mid and right from mid+1, taking the maximum on each side, then summing them.

The recursion has depth O(log n) and each level does O(n) work for the crossing computation, giving O(n log n) total time. Space is O(log n) for the recursion call stack. The base case is a single element, which returns that element. The return value at each level is max(leftResult, rightResult, crossingSum). This cleanly handles the three-case decomposition at every subproblem.

The divide-and-conquer solution is more complex to implement than Kadane's and is strictly worse in time complexity (O(n log n) vs O(n)). Its value is pedagogical: it demonstrates the crossing-subarray pattern, the three-way split at the midpoint, and how D&C can solve problems that seem to require knowing the entire array at once. The crossing computation — scanning left from mid and right from mid+1 greedily — is the unique insight that makes the approach work.

Maximum Subarray (LeetCode 53) and Best Time to Buy and Sell Stock (LeetCode 121) are mathematically equivalent problems. Given stock prices = [7, 1, 5, 3, 6, 4], define the daily change array as changes = [prices[i] - prices[i-1]] = [-6, 4, -2, 3, -2]. The maximum profit from one buy-sell transaction equals the maximum subarray sum of the daily changes array. Applying Kadane's to changes = [-6, 4, -2, 3, -2] gives 4 + (-2) + 3 = 5, which is the correct max profit (buy at 1, sell at 6).

Conversely, the min-price tracking approach for LeetCode 121 implicitly does what Kadane's does on the daily changes: it accumulates gains as long as they are positive and discards the accumulated sum when a better starting point (a new minimum price) is found. Both algorithms make the same extend-or-restart decision — just expressed in different terms.

Understanding this equivalence is a hallmark of strong algorithmic insight and frequently appears as a follow-up question in interviews. It demonstrates that the same underlying optimization — maximize a contiguous sum — appears in multiple guises across the LeetCode problem set. If you can solve one, you can derive the other in seconds.

Python — Kadane's: def maxSubArray(nums): currentSum = maxSum = nums[0]; for num in nums[1:]: currentSum = max(num, currentSum + num); maxSum = max(maxSum, currentSum); return maxSum. Four lines of core logic, O(n) time, O(1) space. Initializing both variables to nums[0] correctly handles all-negative arrays. The loop starts at index 1 since nums[0] is already accounted for. For the divide-and-conquer follow-up, define a helper crossSum(nums, left, mid, right) that scans left from mid and right from mid+1, then recursively calls maxSubArray on the two halves and returns max(leftResult, rightResult, crossSum).

Java — Kadane's: public int maxSubArray(int[] nums) { int currentSum = nums[0]; int maxSum = nums[0]; for (int i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; }. The enhanced loop is replaced with an index loop so we can start from i=1. Both Python and Java solutions handle all-negative inputs, single-element inputs, and all-positive inputs correctly.

Common mistakes to avoid: initializing maxSum to Integer.MIN_VALUE or -infinity works but is fragile and confusing — initializing to nums[0] is cleaner and more readable. Do not initialize currentSum to 0 — if all elements are negative, the algorithm would incorrectly return 0 instead of the largest element. The nums[0] initialization is the canonical pattern for this family of problems.

Best Time to Buy and Sell Stock (LeetCode 121) is the direct equivalent of Maximum Subarray via the daily gains transformation. Both reduce to maximizing a contiguous sum — one over raw values, one over price differences. Subarray Sum Equals K (LeetCode 560) is a cousin problem: instead of maximizing the subarray sum, it counts subarrays with an exact target sum, solved using a prefix sum hashmap. Product Except Self (LeetCode 238) applies a similar prefix-and-suffix scan pattern to products rather than sums.

Kadane's algorithm defines a family: Maximum Product Subarray (LeetCode 152) extends Kadane's to products, requiring tracking both the current maximum and current minimum (since a negative times a negative becomes positive). Maximum Sum Circular Subarray (LeetCode 918) extends to circular arrays by taking max(kadane_normal, totalSum - kadane_minimum). Each problem adds one twist to the core Kadane pattern.

House Robber (LeetCode 198) shares the rolling-variable DP pattern: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) compressed to two variables. Climbing Stairs (LeetCode 70) is the same Fibonacci-style two-variable rolling DP. All of these problems share the same algorithmic skeleton: define a recurrence, observe it depends only on a fixed number of previous states, and compress the DP table to those states. Maximum Subarray is the cleanest single-variable compression in the entire canon.