跳至主要內容

最大子数组和：Kadane算法与分治的深度对比

老张2026/4/30大约 8 分钟

最大子数组和：Kadane算法与分治的深度对比

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

有一年公司的年终晚会抽奖，我们组把当年每周的"KPI得分变化"做成了一个数组（正数是超额完成，负数是没达标），有人说"找一下我们今年哪个连续时间段绩效最好"。

这不就是最大子数组和的现实版本吗？

我当场在手机备忘录上写了三行 Kadane 算法，把数组递给他，说找那段最大连续和对应的时间段就是了。旁边的测试同学问："这什么算法？怎么这么短？"我说："Kadane，O(n)，动态规划的简化版。"她表示不信，觉得这么简单的几行代码不可能是 O(n) 的正确算法。

第二天我专门写了一篇解析给她看，从暴力到 Kadane 的推导过程。这篇文章就是那篇解析的升级版。

LeetCode 53 的 Kadane 算法是我见过的最优雅的动态规划简化之一——几乎所有人第一次见到都会觉得"这也太简单了吧"，但真正理解为什么它是对的，需要理清状态定义和转移方程。

一、题目解析

LeetCode 53. 最大子数组和（Maximum Subarray）

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入输出示例：

示例 1（经典情况）：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

示例 2（全正数）：

输入：nums = [1]
输出：1

示例 3（全负数）：

输入：nums = [-1,-2,-3]
输出：-1
解释：全负数时，最大子数组和就是最大的那个单一负数

边界情况 4（单个正数）：

输入：nums = [5]
输出：5

边界情况 5（有大正数和大负数）：

输入：nums = [100,-101,100]
输出：100
解释：两端的 100 不能合并，中间的 -101 隔断了它们

考察的核心知识点：

  • 动态规划状态定义
  • Kadane 算法（DP 的空间优化版）
  • 分治法：跨越中点的子数组
  • 全负数的边界处理

二、解法一：暴力解法

思路分析

枚举所有子数组的起点和终点，计算每个子数组的和，取最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

时间复杂度：O(n²)，空间复杂度：O(1)。

三、解法二：动态规划（标准 DP 写法）

思路分析

定义 dp[i] = 以 nums[i] 结尾的最大子数组和。

状态转移：dp[i] = max(dp[i-1] + nums[i], nums[i])

含义：以 nums[i] 结尾的子数组，要么把 nums[i] 接在以 nums[i-1] 结尾的最大子数组后面，要么就从 nums[i] 重新开始。如果 dp[i-1] < 0，接上去只会让总和更小，不如从 nums[i] 重新开始。

最终答案：max(dp[0], dp[1], ..., dp[n-1])。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int maxSum = dp[0];
        
        for (int i = 1; i < n; i++) {
            // 要么接在前面，要么重新开始
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)，dp 数组。

四、解法三：Kadane 算法（空间优化 DP）

核心洞见

观察标准 DP 的转移：dp[i] 只依赖于 dp[i-1]，不需要存整个 dp 数组，只用一个变量记录 dp[i-1] 就够了。

class Solution {
    public int maxSubArray(int[] nums) {
        int curMax = nums[0];  // dp[i]，以当前元素结尾的最大子数组和
        int maxSum = nums[0];  // 历史最大值
        
        for (int i = 1; i < nums.length; i++) {
            // Kadane 核心：如果前面的和是负的，直接放弃，从当前重新开始
            curMax = Math.max(curMax + nums[i], nums[i]);
            // 等价于：curMax = nums[i] + Math.max(curMax, 0);
            maxSum = Math.max(maxSum, curMax);
        }
        return maxSum;
    }
}

时间复杂度：O(n)，空间复杂度：O(1)。

我在 LeetCode 提交，运行时间 1ms，击败 99.8% 的 Java 用户。

为什么 curMax = nums[i] + Math.max(curMax, 0) 更直观？

如果前面的和 curMax > 0，加上当前元素能增大总和，接上。如果 curMax <= 0，接上会减小或不变，不如从 nums[i] 重新开始（curMax = nums[i] + 0 = nums[i]）。

五、解法四：分治法（O(n log n)，面试高分点）

核心思路

将数组分成左右两半。最大子数组要么在左半部分，要么在右半部分，要么跨越中点。

跨越中点的最大子数组：从中点向左找最大连续和 + 从中点+1向右找最大连续和。

递归解决左右两半，合并结果，取三者最大。

class Solution {
    public int maxSubArray(int[] nums) {
        return divideAndConquer(nums, 0, nums.length - 1);
    }
    
    private int divideAndConquer(int[] nums, int left, int right) {
        if (left == right) return nums[left];
        
        int mid = left + (right - left) / 2;
        
        // 左半部分的最大子数组和
        int leftMax = divideAndConquer(nums, left, mid);
        // 右半部分的最大子数组和
        int rightMax = divideAndConquer(nums, mid + 1, right);
        // 跨越中点的最大子数组和
        int crossMax = maxCrossing(nums, left, mid, right);
        
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
    
    // 计算跨越 mid 的最大子数组和
    private int maxCrossing(int[] nums, int left, int mid, int right) {
        // 从 mid 向左扩展，找最大前缀和
        int leftSum = 0, maxLeft = Integer.MIN_VALUE;
        for (int i = mid; i >= left; i--) {
            leftSum += nums[i];
            maxLeft = Math.max(maxLeft, leftSum);
        }
        
        // 从 mid+1 向右扩展，找最大后缀和
        int rightSum = 0, maxRight = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= right; i++) {
            rightSum += nums[i];
            maxRight = Math.max(maxRight, rightSum);
        }
        
        return maxLeft + maxRight;
    }
}

时间复杂度：O(n log n)

推导：T(n) = 2T(n/2) + O(n)（跨越中点的计算是 O(n)），由主定理知 T(n) = O(n log n)。

空间复杂度：O(log n)，递归栈深度。

六、举一反三

同类型题目

LeetCode 918. 环形子数组的最大和

数组是循环的，最大子数组可以跨越数组末尾。关键：max(普通最大子数组, 总和 - 最小子数组和)。注意全负数时特殊处理。

LeetCode 152. 乘积最大子数组

改为乘积，需要同时维护最大乘积和最小乘积（负数乘负数变正数）。

LeetCode 124. 二叉树中的最大路径和

树形版的最大路径和，用后序遍历，每个节点维护"以该节点为端点的最大路径和"。

LeetCode 1186. 删除一次得到子数组最大和（付费题）

允许删除一个元素，找最大子数组和。DP 状态需要多一维记录是否已经删除过。

面试中的变体和追问

  1. 如何返回最大子数组本身（不只是和）？ 答：额外维护起始下标。当 curMax < 0 时重新开始，记录新起点；每次 curMax > maxSum 时更新答案的起点和终点。

  2. Kadane 算法处理全负数的情况？ 答：能正确处理。初始化 maxSum = nums[0]（不是 0 或 Integer.MIN_VALUE），循环从 i=1 开始，全负数时 curMax 始终等于单个元素值，maxSum 取所有元素中的最大值（绝对值最小的负数），正确。

七、踩坑实录

坑一：maxSum 初始化为 0 导致全负数答案为 0

现象： 输入 [-3,-1,-2]，期望 -1，输出 0。

原因： maxSum = 0 的初始化，在全负数时，maxSum 不会被更新（所有子数组和都 < 0），返回了错误的 0。题目要求子数组至少包含一个元素，空数组（和为0）不合法。

解法： 初始化 maxSum = nums[0]，循环从 1 开始。或者初始化 maxSum = Integer.MIN_VALUE，效果相同，但前者更直观。

坑二：分治法中跨越中点的合并逻辑

现象： 分治版本在某些边界输入上返回错误结果。

原因： 跨越中点时，左侧从 mid 向左找，右侧从 mid+1 向右找。如果左侧或右侧全负，maxLeft/maxRight 仍然是某个负数（初始化为 Integer.MIN_VALUE 保证了这一点），两个负数相加会小于任意一个单独的值，但分治的合并里三者取最大，最终还是正确的。

坑在于：如果把 maxLeft/maxRight 初始化为 0，那么跨越中点的结果会偏大（把空子数组算进去了）。

坑三：Kadane 算法的等价写法混淆

// 写法一（原版）
curMax = Math.max(curMax + nums[i], nums[i]);

// 写法二（等价，更直观）
curMax = nums[i] + Math.max(curMax, 0);
// 或
if (curMax < 0) curMax = 0;
curMax += nums[i];

写法三（if (curMax < 0) curMax = 0）必须在加 nums[i] 之前执行，不能在之后。顺序搞错就不对了。

八、总结

最大子数组和是动态规划的入门经典题，Kadane 算法把 O(n²) 暴力直接降到 O(n) O(1)，思路简洁优美。

三条核心要点：

  1. Kadane 算法的核心逻辑：以当前元素结尾的最大子数组和，等于"前面的最大子数组和（如果非负就接上，如果负就丢弃）+ 当前元素"。这一句话说清楚了所有状态转移。

  2. 初始化必须用 nums[0]，不能用 0 或负无穷（虽然负无穷也行，但 nums[0] 最直观）。全负数时答案就是最大的单个元素。

  3. 分治法虽然时间 O(n log n) 不如 Kadane 的 O(n)，但它展示了一种通用的"跨越中点"思维，在二叉树最大路径和等题目里是标准方法。

延伸思考：

Kadane 算法的思想——"如果前面的结果是负的就丢弃，从当前位置重新开始"——在时间序列分析中是一个通用模式。股票分析、信号处理、自然语言处理中的滑动窗口评估，很多地方都能看到这个思想的影子。

编辑此页
最近更新:
贡献者: xiaozhangge