分治进阶：跨越中点，以及只走一边

分治三步（和第 11 章一模一样的框架）：

最大子段 = 三者取最大：
   ① 完全落在左半边的      → 递归
   ② 完全落在右半边的      → 递归
   ③ 跨过中点的            → 唯一要动脑的部分

跨过中点的那一段，一定是这个形状：

[ ...... mid ][ mid+1 ...... ]
   └─── 左边以 mid 结尾的一段 ───┘ └─── 右边以 mid+1 开头的一段 ───┘

既然它必须同时包含 mid 和 mid+1，那两截就是独立的： 左边取「以 mid 结尾的最大和」，右边取「以 mid+1 开头的最大和」，加起来就是最优。

而这两截都可以从中点往外扫一遍求出来，各 O(长度)：

// 从 mid 往左走，一路累加，记住最大值
long long sum = 0, leftBest = LLONG_MIN;
for (int i = mid; i >= l; i--) { sum += a[i]; leftBest = max(leftBest, sum); }

T(n) = 2T(n/2) + O(n) —— 和归并排序同一个式子，所以是 O(n log n)。

分治不是万能的。 具体到最大子段和，O(n) 的扫描完胜 O(n log n) 的分治， 而且代码只有两行。

那学分治还有什么用？

因为「跨越中点怎么算」这套思维，在别的题上是唯一出路 —— 比如平面最近点对、比如某些区间统计题。工具箱里要有它， 但拿到题先想有没有更简单的办法，再考虑上工具。

顺带说一句：上面那两行其实就是动态规划 —— cur 是「以 i 结尾」这个状态，那个 max 就是状态转移方程。 第 21 章会正式讲它。你已经不知不觉写过一次 DP 了。

用第 10 章快排的划分：随机选一个基准，把小的甩左边、大的甩右边。 划分完之后基准就在它最终的位置 p 上了。

于是：

左边（含基准）有 leftLen 个数：

  k == leftLen  →  基准就是第 k 小，直接返回
  k <  leftLen  →  第 k 小在左边，右边整片**再也不看了**
  k >  leftLen  →  第 k 小在右边，左边整片**再也不看了**，且在新区间里找第 k-leftLen 小

快排两边都要继续，这里只要一边。

工作量：n + n/2 + n/4 + … = 2n。所以平均是 O(n)，比排序还快一个 log。

这种「每次砍掉一部分、只在剩下的里面继续」的套路有个专门的名字： 减治（decrease and conquer），区别于两边都要处理的分治。

第 8 章的二分其实就是减治的极端版本 —— 它每一步只做 O(1) 的工作，所以是 O(log n)。

1. 分治三步：分 → 治 → 合。 分和治是套路，「合」才是每道题的真正内容。
2. 先问「跨越中点的那部分怎么算」。 算得出来就能分治，算不出来就别硬套。
3. 如果只需要递归一边，那是减治，复杂度会掉一个数量级（O(n log n) → O(n)， 或者 O(n) → O(log n)）。
4. 分治不是越用越好。 最大子段和有 O(n) 的扫描，第 k 小比赛里直接 nth_element。 工具箱里有它，但先想有没有更简单的路。