Maximum Subarray (D&C) medium
Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Examples
> Case 1:
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: [4, -1, 2, 1] has the largest sum = 6.
> Case 2:
nums = [1]
Output: 1
> Case 3:
nums = [5, 4, -1, 7, 8]
Output: 23Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Follow-up: if you have figured out the O(n) solution (Kadane’s), try the divide and conquer approach.
Why this is a D&C classic
The O(n) Kadane’s algorithm (covered on Day 14) is the right interview answer. But the D&C formulation is a textbook example of the “left / right / crossing” pattern.
State design
The max subarray is one of three things:
- Entirely in the left half.
- Entirely in the right half.
- Crosses the midpoint — starts somewhere in the left, ends somewhere in the right.
Cases 1 and 2 are recursive subproblems. Case 3 requires computing the best suffix of the left half ending at mid plus the best prefix of the right half starting at mid + 1. Both can be done in one pass through the relevant half.
Recurrence: T(n) = 2 T(n / 2) + O(n) → O(n log n).
Code
Why is the crossing computed by scanning from the midpoint outward? Because the crossing subarray must include the midpoint (it crosses there). So the best left part is the best suffix of [lo..mid] ending at mid, and the best right part is the best prefix of [mid+1..hi] starting at mid+1. Both can be computed in one linear pass through the relevant half.
Comparison to Kadane’s
def max_subarray_kadane(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return bestO(n) time, O(1) space. Strictly better than D&C for this specific problem. The D&C version is worth knowing because the “left / right / crossing” framing generalizes to problems where Kadane’s O(n) trick doesn’t apply — for example, when you also need to track positions, or when you’re working on a 2D grid.
Analysis
- Time:
O(n log n). - Space:
O(log n)recursion.
Same skin
- Maximum Subarray Sum on 2D Matrix — D&C on rows + Kadane on columns.
- Closest Pair of Points — same “left / right / crossing” framing, with a different combine.
- Inversion Counting — left / right / cross, with the cross step counting pairs straddling the midpoint.
- Counting Inversions Beyond a Threshold — same framing.