Maximum Subarray Problem
You'll learn how to find the contiguous subarray with the largest sum using divide and conquer, carefully handling elements that cross the middle boundary.
What's the Problem?
Given an array of numbers (possibly negative), find the contiguous subarray whose elements add up to the maximum possible sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is [4, -1, 2, 1] with sum 6.
The Divide and Conquer Approach
Like Mergesort and Quicksort, we split the array in half. The maximum subarray must be in one of three places:
- Entirely in the left half
- Entirely in the right half
- Crossing the midpoint (starts in left, ends in right)
The first two cases are solved recursively. The tricky part is the third case.
Handling the Cross-Boundary Case
Think of it like two treasure hunters starting at the middle of a bridge and walking opposite directions, each collecting coins as they go. One walks left, tracking their best haul. The other walks right, doing the same. Together, their combined best finds give you the maximum crossing subarray.
To find the maximum crossing subarray:
- Start at the midpoint, extend left, keeping a running sum and tracking the best sum seen
- Do the same extending right from the midpoint
- Add these two best sums together
Then compare all three possibilities (left-only, right-only, crossing) and return the maximum.
Why This Works
Every contiguous subarray either stays within one half or crosses the boundary—there's no fourth option. By recursively solving the halves and carefully computing the crossing case, we cover all possibilities.
Key Takeaway: The Maximum Subarray Problem uses divide and conquer by splitting the array and explicitly computing the maximum sum that crosses the midpoint, then comparing it with recursive solutions from each half.