Maximum Subarray
Given an integer array nums1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
The page gives two solutions.
Example 1
Output: 6
Explanation: the subarray [4, -1, 2, 1] has the largest sum.
Example 2
Output: 1
Example 3
Output: 23
Explanation: the whole array is the best subarray.
How to Think About It
Step 1: Check every subarray
A subarray is fixed by its first index i and its last index j. There are about n^2 / 2 such pairs. Summing each pair from scratch costs O(n) more, which gives O(n^3).
Step 2: Reuse the running sum
For a fixed start i, the sum of nums[i..j+1]nums[i..j]nums[j+1]
Step 3: Ask a smaller question at each index
Instead of asking about every pair, ask: what is the best sum of a subarray that ends exactly at index i? Call it currentnums[i]
current = max(nums[i], current + nums[i])
Why is extending the best one enough? Any subarray ending at i that includes i - 1 has the form (something ending at i - 1) plus nums[i]current
Step 4: A negative prefix is dead weight
Read the formula in words: if the running sum before i is negative, it only drags nums[i]current
This is a one-variable dynamic programming recurrence, known as Kadane's algorithm. The
Walkthrough
Solution 2 on Example 1, nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]nums[0] = -2
| i | nums[i] | Choice | current | best |
|---|---|---|---|---|
| 0 | -2 | first element | -2 | -2 |
| 1 | 1 | start fresh, -2 + 1 is worse than 1 | 1 | 1 |
| 2 | -3 | extend | -2 | 1 |
| 3 | 4 | start fresh, -2 + 4 is worse than 4 | 4 | 4 |
| 4 | -1 | extend | 3 | 4 |
| 5 | 2 | extend | 5 | 5 |
| 6 | 1 | extend | 6 | 6 |
| 7 | -5 | extend | 1 | 6 |
| 8 | 4 | extend | 5 | 6 |
The best value, 6, was reached at index 6. The run that produced it started at index 3, which is the subarray [4, -1, 2, 1].
Solution 1: Brute Force
This method fixes each start index in turn and extends the subarray one element at a time, keeping a running sum.
- The running sum:
is reset to 0 for each new startsum , then grows byi , so it always equals the sum ofnums[j] .nums[i..j] - Checking after every add:
is compared after each step of the inner loop, so every subarray, including single elements, is considered.best - Starting value of best:
is lower than any real sum, so the first subarray always replaces it.Integer.MIN_VALUE - Large inputs: at
the inner statement runs about 5 × 10^9 times. A test run on 10^5 elements took about 3 seconds, which is too slow for LeetCode's largest tests.n = 10^5
A common mistake is to start with best = 0[-3, -1, -2]
public class MaximumSubarrayBruteForce {
public int maxSubArray(int[] nums) {
int best = Integer.MIN_VALUE; // lower than any real sum
for (int i = 0; i < nums.length; i++) {
int sum = 0; // sum of nums[i..j]
for (int j = i; j < nums.length; j++) {
sum += nums[j];
best = Math.max(best, sum);
}
}
return best;
}
public static void main(String[] args) {
MaximumSubarrayBruteForce solver = new MaximumSubarrayBruteForce();
System.out.println(solver.maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 6
System.out.println(solver.maxSubArray(new int[] {5, 4, -1, 7, 8})); // 23
}
}
Solution 2: Kadane's Algorithm
Kadane's algorithm walks the array once and keeps the best sum of a subarray that ends at the current index, plus the best sum seen anywhere.
- Seeding with the first element:
andcurrent both start atbest , and the loop starts at index 1. A one-element array such as Example 2 returns that element.nums[0] - Extend or restart:
restarts exactly when the oldMath.max(nums[i], current + nums[i]) is negative, because only then is adding it worse than leaving it out.current - All negative numbers: every step restarts, so
is justcurrent andnums[i] becomes the largest element.best returns -1.[-3, -1, -2] - No overflow: the largest possible sum is 10^5 × 10^4 = 10^9, which fits in an
.int
A common mistake is to start currentnums[0]
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int current = nums[0]; // best sum of a subarray ending at index i
int best = nums[0]; // best sum seen anywhere so far
for (int i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]); // restart if the old run is negative
best = Math.max(best, current);
}
return best;
}
public static void main(String[] args) {
MaximumSubarray solver = new MaximumSubarray();
System.out.println(solver.maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 6
System.out.println(solver.maxSubArray(new int[] {1})); // 1
System.out.println(solver.maxSubArray(new int[] {5, 4, -1, 7, 8})); // 23
}
}
Complexity
- Solution 1 time: O(n^2). For each of the n start indices the inner loop runs to the end of the array, so it does n + (n - 1) + ... + 1 = n(n + 1) / 2 constant-time steps.
- Solution 1 space: O(1). Only the two loop indices, the running
andsum are stored, and none of them depend on the array length.best - Solution 2 time: O(n). The single loop visits each index from 1 to n - 1 once and does two
calls per visit, with no inner loop.Math.max - Solution 2 space: O(1). The recurrence only needs the answer for index i - 1, so one variable
replaces a whole dp array.current
Which One to Use
Use Kadane's algorithm in practice and in interviews: it is just as short, runs in linear time, and passes the 10^5 limit easily. The brute force is still worth writing once, because it is obviously correct and makes a good reference to test Kadane's algorithm against. Both always return the same sum, since each considers every subarray, one directly and one through the recurrence. The brute force has one advantage: it visits every subarray explicitly, which helps when a problem asks about all subarrays rather than just the best one.
The same idea with a wrap-around twist is