Maximum Subarray
Problem
nums (which may contain negatives), pick a
non-empty contiguous block of elements whose sum is as large as possible and return
that sum.[-2,1,-3,4,-1,2,1,-5,4]Output6 ([4,-1,2,1])[1]Output1[5,4,-1,7,8]Output231 ≤ n ≤ 105 · -104 ≤ nums[i] ≤ 104 · Follow-up: also try divide and conquer.
Try it yourself
class Solution {
public int maxSubArray(int[] nums) {
}
}
i-1 or starts fresh at nums[i] — a negative running sum can
only hurt, so drop it.Instinct Best sum or product of a contiguous subarray in one pass? At each index choose - extend the run ending here or restart - and track the global best.
Memory hack Carry the bag only while it helps - a negative past is dead weight, drop it and restart here.
Open the Kadane's Running Best guide →Approaches
Brute ForceAll Subarrays, Running Sum
O(n2)Space O(1)Fix each start i and extend j to the right, adding
nums[j] to a running sum so each subarray costs O(1). Track the maximum
over all O(n2) subarrays.
public int maxSubArray(int[] nums) { int maxSum = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { int currentSum = 0; for (int j = i; j < nums.length; j++) { currentSum += nums[j]; // sum of nums[i..j] maxSum = Math.max(maxSum, currentSum); } } return maxSum; }
Simple, but ~5·109 steps at n = 105 — TLE.
BetterDivide and Conquer
O(n log n)Space O(log n)Split at mid. The answer lies entirely in the left half, entirely
in the right half, or crosses mid. The crossing best = best suffix of the left
+ best prefix of the right, found by an O(n) scan. T(n) = 2T(n/2) + O(n).
public int maxSubArray(int[] nums) { return solve(nums, 0, nums.length - 1); } private int solve(int[] a, int lo, int hi) { if (lo == hi) return a[lo]; int mid = (lo + hi) >>> 1; int leftBest = Integer.MIN_VALUE, rightBest = Integer.MIN_VALUE; for (int i = mid, sum = 0; i >= lo; i--) leftBest = Math.max(leftBest, sum += a[i]); for (int i = mid + 1, sum = 0; i <= hi; i++) rightBest = Math.max(rightBest, sum += a[i]); int cross = leftBest + rightBest; // best subarray spanning mid return Math.max(cross, Math.max(solve(a, lo, mid), solve(a, mid + 1, hi))); }
Answers the follow-up and parallelises, but is slower than one linear pass.
OptimalKadane’s Algorithm
O(n)Space O(1)cur = best sum of a subarray ending at i:
cur = max(nums[i], cur + nums[i]). This is a 1-D DP where only the previous
state matters, so one variable suffices. best is the max cur
ever seen; starting from nums[0] handles all-negative arrays.
public int maxSubArray(int[] nums) { int currentSum = nums[0], maxSum = nums[0]; for (int i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); // extend or restart maxSum = Math.max(maxSum, currentSum); } return maxSum; }
Dry run[-2,1,-3,4,-1,2,1,-5,4]
- i=0-2i1-34-121-54cur=-2, best=-2
- i=1-21i-34-121-54restart: cur=1, best=1
- i=3-21-34i-121-54cur=-2 → restart: cur=4
- i=5-21-34-12i1-54cur=3→5, best=5
- i=6-21-34-121i-54cur=6, best=6
- i=8-21-34-121-54icur=1→5, best=6 ✔
One pass, constant space — the expected answer.
start whenever you restart
and copy it into bestStart when best improves.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | All Subarrays, Running Sum | O(n2) | O(1) |
| Better | Divide and Conquer | O(n log n) | O(log n) |
| Optimal | Kadane’s Algorithm | O(n) | O(1) |
- Initialising
maxSum = 0— returns 0 for all-negative input like[-3,-1]. - Resetting
curto 0 before updatingbest— loses negative answers. - Confusing subarray (contiguous) with subsequence (sum of all positives).
- Frame it as DP:
dp[i] = max(nums[i], dp[i-1] + nums[i]), then compress to O(1). - Ask whether an empty subarray is allowed (here it is not).
- Mention D&C for the follow-up and why it is O(n log n).