Maximum Subarray
Last Updated: March 22, 2026
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.
What makes this tricky is that negative numbers can appear anywhere. A subarray like [4, -1, 2, 1] has a sum of 6, which is better than just [4] alone, even though there's a -1 in the middle. So we can't simply skip all negatives. The question becomes: when is it worth absorbing a negative number to reach larger positives later, and when should we cut our losses and start fresh?
That's the key tension in this problem, and each approach handles it differently.
Key Constraints:
nums.lengthup to10^5means O(n^2) would mean up to 10^10 operations, which will time out. We need O(n log n) or better.- Elements can be negative (
-10^4 <= nums[i] <= 10^4), so we can't simply skip negatives or use a sliding window that assumes monotonic growth. - The array is guaranteed non-empty (length >= 1), so we always have at least one valid subarray.
Approach 1: Brute Force
Intuition
The most straightforward way is to check every possible subarray and find which one has 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. This way we don't recalculate the sum from scratch for every subarray, which saves a loop compared to the truly naive O(n^3) approach.
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.
For every starting index, we scan forward through the rest of the array. What if, instead of checking every pair, we could process each element exactly once and decide on the spot whether to extend the current subarray or start fresh?
Approach 2: Kadane's Algorithm
Intuition
Here's the key insight: 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.
You're standing at index i, and you know the best subarray sum that ends at index i-1. You have two choices:
- Extend: Add
nums[i]to the previous subarray. This gives youpreviousBestSum + nums[i]. - Start fresh: Begin a new subarray at
nums[i]. This gives you justnums[i].
When should you start fresh? When previousBestSum is negative. A negative running sum would only drag down whatever comes next. So the decision rule is simple: currentSum = max(nums[i], currentSum + nums[i]).
While making this local decision at every index, we also track the global maximum across all positions. That global maximum is our answer.
Kadane's algorithm is really dynamic programming in disguise. If we define dp[i] as the maximum subarray sum ending at index i, then the recurrence is: dp[i] = max(nums[i], dp[i-1] + nums[i]). The answer is the maximum value across all dp[i]. Since dp[i] only depends on dp[i-1], we don't need an array at all. A single variable currentSum is enough. That's why the space complexity is O(1).
The beauty of this approach is that it never looks backward. At each index, it makes the locally optimal choice (extend or restart), and the global maximum captures the best subarray found during the entire scan.
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 already O(n), which is optimal for this problem since we must look at every element at least once. But the problem asks for a divide and conquer approach as a follow-up. It won't beat Kadane's in time complexity (it's O(n log n)), but it demonstrates a different way of thinking about the problem.
Approach 3: Divide and Conquer
Intuition
The divide and conquer approach splits the array at the midpoint and makes a recursive observation: the maximum subarray is in one of three places:
- Entirely in the left half
- Entirely in the right half
- Crossing the midpoint (starts in the left half, ends in the right half)
We recursively solve the left and right halves. The crossing case is the interesting part: we find the best suffix of the left half (extending from mid leftward) and the best prefix of the right half (extending from mid+1 rightward), then combine them.
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.