Maximum Subarray (D&C)

Finds the contiguous subarray with maximum sum. Divide & conquer variant reveals structural decomposition (left, right, crossing) although Kadane achieves linear time. Useful for teaching recurrence construction and crossing computations.

Recurrence & Intuition

Split into halves; solve recursively; compute crossing in linear time by scanning outward from midpoint. Master theorem on T(n)=2T(n/2)+O(n) gives O(n log n).

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

Applications

• Financial time series: peak contiguous gain window.
• Signal/noise analysis: strongest burst detection.
• Dynamic programming primer (transition to Kadane).
• Teaching crossing combination patterns in recurrences.