最大子陣列問題（maximum subarray）

假設某股票每日的價格變動寫成一串獲利與虧損，例如 [-2, +5, -1, +3, -4]。你想找總獲利最大的單一「先買後賣」區間——等價於陣列中和最大的連續切片。暴力法嘗試全部 O(n^2) 個起訖配對；分治法則利用最佳切片相對於陣列中點可能落在何處，做得更好。

把陣列在中間切成左半與右半。和最大的連續子陣列必定恰好是三者之一：完全在左半、完全在右半、或橫跨中點。前兩者由遞迴解決。橫跨的情況是合併步驟，也是唯一巧妙之處：跨越中點的子陣列必定包含左半的最右元素與右半的最左元素，所以你從中間向左掃描累積最佳左延伸、向右掃描累積最佳右延伸，再把兩者相加。每趟掃描是 O(n)，故合併是 O(n)，得 T(n) = 2 T(n/2) + O(n) = O(n log n)。整個問題的答案是這三個候選的最大值。

這是一個乾淨的課堂示例，說明合併步驟如何承載關鍵洞見——橫跨的情況正是兩個遞迴呼叫各自看不到的。但誠實地補充：最大子陣列有更好的解法：Kadane 演算法，一趟的動態規劃掃描，以 O(n) 時間與 O(1) 空間解決。因此分治版本被珍視為這個範式的教學範例，而非你會實際採用的演算法；當問題具有重疊結構時，動態規劃的觀點能勝過分治的觀點。