Maximum Subarray (D&C) Theory

Compute the maximum contiguous subarray sum using the divide & conquer strategy. Illustrates combining local segment solutions via a crossing structure (suffix + prefix) and contrasts with linear DP (Kadane). Useful for mastering recurrence derivation and boundary reasoning.

Divide & Conquer Structure

1. Split at midpoint m.
2. Solve left half best.
3. Solve right half best.
4. Compute best crossing: suffix(left) + prefix(right).
5. Take maximum of (left, right, crossing).

Recurrence

T(n)=2T(n/2)+O(n) → O(n log n)

• Linear crossing computation dominates merge step.
• Master theorem case 2 with a=2, b=2, f(n)=n.
• Stack depth O(log n) from balanced splits.

Pseudocode

1function maxSubarray(arr):
2  if length(arr) == 1: return arr[0]
3  mid = length(arr)//2
4  leftBest = maxSubarray(arr[0:mid])
5  rightBest = maxSubarray(arr[mid:])
6  crossBest = bestCrossing(arr, mid)
7  return max(leftBest, rightBest, crossBest)

Comparing With Kadane

• Kadane runs in O(n) maintaining best ending-at-i prefix.
• Divide & conquer clarifies structural case partition (left/right/cross).
• Pedagogical: sets stage for DP vs structural recursion tradeoffs.
• Crossing computation idea generalizes to other combination schemes.

Edge Considerations

• All negative: correct answer is largest (least negative) element.
• Ensure crossing includes one element from each side (avoid double counting).
• Indices often tracked for reconstruction (store start/end from each scan).