the maximum-subarray problem

Suppose a stock's daily price changes are written as a list of gains and losses, like [-2, +5, -1, +3, -4]. You want the single buy-then-sell window with the biggest total gain — equivalently, the contiguous slice of the array with the largest sum. Brute force tries all O(n^2) start/end pairs; divide and conquer does better by exploiting where the best slice can possibly sit relative to the array's midpoint.

Split the array at the middle into a left half and a right half. The maximum-sum contiguous subarray must be one of exactly three things: entirely in the left half, entirely in the right half, or crossing the midpoint. The first two are solved by recursion. The crossing case is the combine step and the only clever part: a subarray that straddles the midpoint must include the rightmost element of the left half and the leftmost element of the right half, so you scan leftward from the middle accumulating the best left extension, scan rightward accumulating the best right extension, and add them. Each scan is O(n), so combine is O(n), giving T(n) = 2 T(n/2) + O(n) = O(n log n). The answer to the whole problem is the maximum of the three candidates.

This is a clean classroom illustration of how the combine step carries the insight — the crossing case is precisely what neither recursive call can see on its own. It is honest to add, though, that maximum-subarray has an even better solution: Kadane's algorithm, a one-pass dynamic-programming scan, solves it in O(n) time and O(1) space. So the divide-and-conquer version is prized as a teaching example of the paradigm rather than as the algorithm you would ship; when a problem has overlapping structure, the DP view can beat the divide-and-conquer view.