← Divide & Conquer

Maximum Subarray (D&C)

Finds the max-sum subarray by dividing the array and combining across the midpoint.

0
1
2
3
4
5
6
7
8
-2
1
-3
4
-1
2
1
-5
4
Active subproblem
Crossing subarray
Best result

Step 1 of 35

Maximum Subarray (Divide & Conquer): split array at midpoint, recurse on each half, find max crossing subarray, return the best of the three.

▶Algorithm
MaxSubarrayDC(arr, lo, hi):
if lo == hi: return arr[lo]
mid = (lo + hi) / 2
left = MaxSubarrayDC(arr, lo, mid)
right = MaxSubarrayDC(arr, mid+1, hi)
cross = MaxCrossing(arr, lo, mid, hi)
return max(left, right, cross)
// maximum subarray found

At each level: find max in left half, right half, and crossing the midpoint. Return the best of the three. O(n log n) time, O(log n) stack space.

1 / 35Speed