如何用分治法求最大子数组和？和 Kadane 算法比怎么样？

简化版

把数组从中间切开，连续的最大子数组和只可能是三种之一：完全落在左半、完全落在右半、或跨越中点。左右两种各自递归求；跨中点的那种，从中点分别向左、向右扩展，求「必过中点的最大后缀和 + 最大前缀和」。三者取最大即答案。递归式 T(n)=2T(n/2)+O(n) → O(n log n)。它比 Kadane（动态规划）的 O(n) 慢，但是理解分治「合并」的经典例题。

详细版

int maxSubArray(int[] a) {
    return divide(a, 0, a.length - 1);
}
int divide(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];               // 递归基：单个元素
    int mid = lo + (hi - lo) / 2;
    int left  = divide(a, lo, mid);            // 情况①：完全在左半
    int right = divide(a, mid + 1, hi);        // 情况②：完全在右半
    int cross = maxCross(a, lo, mid, hi);      // 情况③：跨越中点
    return Math.max(Math.max(left, right), cross);
}
// 求「必须跨越中点」的最大子数组和
int maxCross(int[] a, int lo, int mid, int hi) {
    int leftSum = Integer.MIN_VALUE, sum = 0;
    for (int i = mid; i >= lo; i--) {          // 从中点向左，含 mid 的最大后缀
        sum += a[i];
        leftSum = Math.max(leftSum, sum);
    }
    int rightSum = Integer.MIN_VALUE; sum = 0;
    for (int i = mid + 1; i <= hi; i++) {      // 从中点+1 向右，最大前缀
        sum += a[i];
        rightSum = Math.max(rightSum, sum);
    }
    return leftSum + rightSum;                 // 两段拼起来，一定连续且过中点
}

三种情况互斥且覆盖所有可能，取最大即可。
跨中点的段必须连续包含中点两侧：左边算「以 mid 结尾的最大后缀」、右边算「以 mid+1 开头的最大前缀」，相加保证连续。
复杂度 O(n log n)，不如 Kadane 的 O(n)，但演示了标准的「分—治—合」结构。

完整版教学

一、问题与三种情况的划分

「最大子数组和」：找一段连续的子数组，使其元素和最大（子数组非空）。例如 [-2,1,-3,4,-1,2,1,-5,4] 的答案是 [4,-1,2,1]，和为 6。

分治的切入点：把区间 [lo, hi] 从中点 mid 切成左右两半，那么最优解（那段连续子数组）和中点的关系只有三种可能：

完全在左半 [lo, mid] 里；
完全在右半 [mid+1, hi] 里；
横跨中点——左端在左半、右端在右半，中间必然连续经过 mid 和 mid+1。

这三种情况不重不漏地覆盖了所有可能，所以答案就是三者的最大值。情况 1、2 天然是「同一个问题的更小版本」，直接递归；情况 3 是分治里要单独处理的「合并」。

二、跨中点的最大和怎么求（关键）

情况 3 是这道题的核心。跨中点的子数组，必须同时包含 mid 和 mid+1，并且连续。所以它一定长成这样：

[ ...一段以 mid 结尾的 ][ 一段以 mid+1 开头的... ]
        左半后缀              右半前缀

于是分两步、各扫一遍：

从 mid 往左逐个累加，记录过程中的最大后缀和 leftSum（这段必须含 mid）；
从 mid+1 往右逐个累加，记录最大前缀和 rightSum（这段必须含 mid+1）；
两者相加，就是「必过中点」的最大子数组和。

因为两段分别贴着中点、方向相反，拼起来必然是一段连续且跨中点的子数组。这一步是 O(n)。

易错点：leftSum、rightSum 的初值要设成负无穷（MIN_VALUE） 而不是 0。若设 0，当所有元素都是负数时会错误地允许「空段」，跨中点段却是必须含中点的，不能为空。

三、递归合并与复杂度 O(n log n)

主函数把三种情况的结果取最大返回。复杂度分析：

每层递归把问题分成 2 个半规模子问题：2T(n/2)；
每层求跨中点的和扫一遍：O(n)；
合起来 T(n)=2T(n/2)+O(n)，由主定理（情况二）得 O(n log n)。

四、和 Kadane（动态规划）O(n) 对比

同一题，Kadane 算法用动态规划只需 O(n)：

int maxSubArray(int[] a) {
    int cur = a[0], best = a[0];
    for (int i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]); // 要么接上前面，要么从我重新开始
        best = Math.max(best, cur);
    }
    return best;
}

Kadane 的状态定义是「以 i 结尾的最大子数组和」cur：要么把 a[i] 接到前面那段后面，要么从 a[i] 自己重新开始，取大者；全程记录最大值。一次遍历、O(n) 时间、O(1) 空间，全面优于分治。

那分治还有什么意义？ 一是它是理解「分—治—合」范式的经典教学题；二是当问题变形（比如求最大子矩阵、或需要维护更复杂的区间信息如线段树维护区间最大子段和）时，分治/区间合并的思路更容易推广，而朴素 Kadane 不好扩展。面试里若被要求「用分治做」，考的就是你会不会处理跨中点这一步。

五、易错点小结

❌ 跨中点段没强制包含中点两侧——必须是「含 mid 的最大后缀 + 含 mid+1 的最大前缀」，不能各自独立取最大。
❌ leftSum/rightSum 初值设 0——全负数组会出错，应设 MIN_VALUE。
❌ 忘了子数组非空的约定——递归基返回 a[lo]（单元素），保证至少一个元素。
❌ 认为分治更优——本题分治 O(n log n) 反而不如 Kadane O(n)，别为用分治而用分治。

六、递归式、合并证明与数字推演

这道题的分治闭环是：最大子数组只可能完全在左、完全在右或跨越中点；跨中点解由左侧最大后缀加右侧最大前缀组成。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=2T(n/2)+Θ(n)=Θ(n log n)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：[-2,1,-3,4,-1,2,1,-5,4] 在相关层跨中点组合 4,-1,2,1 得 6。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：全负数组不能把空数组和 0 当答案；求下标需在合并时同步记录边界。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

八、常见误区与追问

误区：跨中点只看 mid 和 mid+1。 应分别向两侧扫描最佳后缀与前缀。
误区：最大子数组允许空数组。 经典定义要求至少一个元素，全负时答案是最大单值。
误区：三种候选可能重叠所以会漏。 它们按是否跨中点完整覆盖所有连续子数组。
追问：为什么 Kadane 更快？ 它在线维护以当前位置结尾的最优值，只需 O(n)。
追问：分治版有什么价值？ 展示分治分类与合并，也能扩展为区间节点的四元信息。
追问：线段树如何关联？ 节点维护总和、最大前缀、最大后缀、最大子段即可合并。

九、加强记忆

最大子数组和的分治：从中点切开，答案是**「全在左半」「全在右半」「跨中点」** 三种取最大。跨中点段 = 含 mid 的最大后缀 + 含 mid+1 的最大前缀（初值取 MIN_VALUE 防全负出错），O(n) 求出。递归式 T(n)=2T(n/2)+O(n) → O(n log n)。它慢于 Kadane 动态规划的 O(n)/O(1)（以 i 结尾的和：接前面 or 从头开始），但作为分治「合并」的范例、以及推广到最大子矩阵/线段树时价值突出。

简化版

详细版