Maximum Subarray
Understanding the Problem
We need to find a contiguous portion of the array whose elements add up to the largest possible sum. The subarray must contain at least one element, so we can't return 0 for an array of all negatives.
The complication is that negative numbers can appear anywhere. A subarray like [4, -1, 2, 1] has a sum of 6, which beats [4] alone, even though there's a -1 in the middle. So we cannot skip all negatives. The question is when it pays to absorb a negative number to reach larger positives later, and when to abandon the current subarray and start a new one. Each approach below resolves that question differently.
Key Constraints:
nums.lengthup to10^5means an O(n^2) scan does up to 10^10 operations and times out. We need O(n log n) or better.- Elements can be negative (
-10^4 <= nums[i] <= 10^4), so we cannot skip negatives or use a sliding window that assumes the sum only grows as the window widens. - The array is non-empty (length >= 1), so there is always at least one valid subarray, and the answer for an all-negative array is the largest single element rather than 0.
Approach 1: Brute Force
Intuition
Check every possible subarray and keep the largest sum. A subarray is defined by its start and end index, so we try every valid pair.
For each starting index i, we extend the subarray one element at a time, adding each new element to a running sum. Reusing this running sum avoids recomputing each subarray's total from scratch, which saves a loop compared to the O(n^3) version that re-sums every subarray.
Algorithm
- Initialize
maxSumto the first element (since the subarray must contain at least one element) - For each starting index
ifrom 0 to n-1: - Initialize
currentSumto 0 - For each ending index
jfromito n-1: - Add
nums[j]tocurrentSum - Update
maxSumifcurrentSumis larger - Return
maxSum
Example Walkthrough
Code
- Time Complexity: O(n^2). The outer loop runs n times, and for each starting index, the inner loop runs up to n times. This gives us roughly n \* n / 2 total operations.
- Space Complexity: O(1). We only use two variables (
maxSumandcurrentSum) regardless of input size.
The brute force repeats work: it recomputes overlapping subarray sums again and again. The next approach processes each element once, deciding at every position whether to extend the current subarray or begin a new one.
Approach 2: Kadane's Algorithm
Intuition
At each position in the array, the maximum subarray ending at that position is either the element itself, or the element plus the maximum subarray ending at the previous position. That single observation removes the need to consider every start index separately.
At index i, with the best subarray sum ending at index i-1 known, there are two choices:
- Extend: Add
nums[i]to the previous subarray, givingpreviousBestSum + nums[i]. - Start a new subarray: Begin again at
nums[i], givingnums[i]alone.
Starting a new subarray wins exactly when previousBestSum is negative, since a negative running sum can only reduce whatever follows. The decision rule is currentSum = max(nums[i], currentSum + nums[i]).
While making this local decision at every index, we track the largest currentSum seen across all positions. That global maximum is the answer.
Kadane's algorithm is dynamic programming. Define dp[i] as the maximum subarray sum that ends at index i. Any subarray ending at i either is nums[i] alone or extends a subarray ending at i-1, so dp[i] = max(nums[i], dp[i-1] + nums[i]). Every subarray ends at some index, so the answer is the maximum dp[i] over all i. Because dp[i] depends only on dp[i-1], the table collapses to a single variable currentSum, which is why the space complexity is O(1).
Algorithm
- Initialize
currentSumandmaxSumboth tonums[0] - For each element from index 1 to n-1:
- Set
currentSumto the larger ofnums[i]andcurrentSum + nums[i] - Update
maxSumifcurrentSumis larger - Return
maxSum
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array exactly once, performing O(1) work at each element (a comparison, an addition, and a max operation).
- Space Complexity: O(1). We only use two variables (
currentSumandmaxSum) regardless of input size.
Kadane's is O(n), which is optimal here since the answer can depend on every element. The problem also lists a divide and conquer follow-up. It runs in O(n log n), slower than Kadane's, but it applies a different paradigm and is the standard divide and conquer treatment of this problem.
Approach 3: Divide and Conquer
Intuition
Split the array at the midpoint. The maximum subarray then falls into exactly one of three cases:
- Entirely in the left half
- Entirely in the right half
- Crossing the midpoint (starts in the left half, ends in the right half)
These three cases cover every possibility, because a subarray either stays on one side of the boundary between mid and mid+1 or straddles it. The left and right cases are solved by recursion. For the crossing case, the subarray must contain both nums[mid] and nums[mid+1], so its best value is the best suffix of the left half ending at mid plus the best prefix of the right half starting at mid+1. We find each by extending outward from the boundary one element at a time. The answer is the largest of the three.
Algorithm
- Base case: If the subarray has one element, return that element
- Find the midpoint
mid - Recursively find the maximum subarray sum in the left half:
leftMax - Recursively find the maximum subarray sum in the right half:
rightMax - Find the maximum crossing subarray sum:
- Starting from
mid, extend left, tracking the best sum:leftCrossMax - Starting from
mid + 1, extend right, tracking the best sum:rightCrossMax - Crossing sum =
leftCrossMax + rightCrossMax - Return the maximum of
leftMax,rightMax, and the crossing sum
Example Walkthrough
Code
- Time Complexity: O(n log n). The recurrence is T(n) = 2T(n/2) + O(n). We split into two halves (2T(n/2)) and do O(n) work for the crossing case. By the Master Theorem, this solves to O(n log n).
- Space Complexity: O(log n). The recursion depth is O(log n) since we halve the array each time. Each stack frame uses O(1) space.