LeetCode 剑指 Offer 42. 连续子数组的最大和

约 5 分钟
文章信息 22 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 图森 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 动态规划 分治
目录

题目描述

✅ 剑指 Offer 42. 连续子数组的最大和

image-20250510210012368

题意分析

给定一个整数数组，要在其中挑出一段「连续」且「非空」的子数组，使这段元素之和最大，返回这个最大和本身，而不是子数组的下标或内容。

「连续」是硬约束：选出的元素必须在原数组中位置相邻，不能跳着挑；这和「任选若干个元素求最大和」是完全不同的问题，后者只要把所有正数加起来即可。

「非空」同样是硬约束：即使整个数组都是负数，也必须选出至少一个元素，此时答案是数组中最大的那个负数，而不是 0。题面允许元素取负值，所以全负数组是必须正面处理的合法输入，不是异常输入。

数组长度至少为 1，所以不存在空数组的退化情况，可以放心用首元素做初始值。数组规模在十万量级，元素绝对值在一万以内，因此总和不会溢出 32 位整数，但也提示了平方级别的枚举会超时，需要线性做法。

边界上要留意三类输入：只有一个元素时直接返回该元素；全负数组时返回最大的负数；含 0 的数组中 0 也是合法元素，不能因为它「不贡献」就跳过。

解法：Kadane 动态规划

核心思路

问题关键：暴力枚举所有区间需要 $O(n^2)$。每个非空子数组都有唯一右端点，因此可以按右端点分组，只求“必须在当前位置结尾”的最优解。

为什么选动态规划：固定右端点后，当前位置的最优解只依赖前一位置的最优结尾，子问题能够复用并在线性时间内递推。

状态与选择：令 cur 表示以 nums[i] 结尾的最大子数组和。这样的子数组只有两种来源：从 nums[i] 重新开始，或把 nums[i] 接到上一位置的最优结尾后，因此

\[cur_i = \max(nums_i, cur_{i-1} + nums_i)\]

直观上，前一段和为正就值得保留，为负只会拖累当前元素，应直接舍弃。再用 ans 记录所有 cur 的最大值；因为 cur 只依赖前一项，无需保存完整 DP 数组。

不变量：处理完下标 i 后，cur 是所有以 i 结尾子数组的最大和，ans 是右端点位于 [0,i] 的所有子数组最大和。

正确性：转移穷尽了以 i 结尾的两种可能，故 cur 正确；ans 收集每一种右端点的最优值，遍历结束即为全局最优。

解题步骤

  1. 用 nums[0] 初始化 cur 和 ans，保证子数组非空，并正确处理全负数组。
  2. 从下标 1 开始，更新 cur = max(nums[i], cur + nums[i])。
  3. 用新的 cur 更新 ans，保留所有右端点中的最好结果。
  4. 遍历结束返回 ans，而不是最后的 cur。

口述样例：[-2,1,-3,4,-1,2,1,-5,4] 的 cur 依次为 -2,1,-2,4,3,5,6,1,5，历史最大值为 6，对应 [4,-1,2,1]。

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0];
        int ans = nums[0];

        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

func maxSubArray(nums []int) int {
    cur := nums[0]
    ans := nums[0]

    for i := 1; i < len(nums); i++ {
        if cur < 0 {
            cur = nums[i]
        } else {
            cur += nums[i]
        }
        if cur > ans {
            ans = cur
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。每个元素只参与一次常数时间的状态转移。
  • 空间复杂度：$O(1)$。只维护 cur 和 ans 两个变量。

关键点总结

  • 状态必须包含“以当前位置结尾”，否则无法判断当前元素能否接到旧答案后面。
  • cur 是局部最优，允许下降或重置；ans 是历史全局最优，二者不能混用。
  • 用首元素初始化而不是 0，这是全负数组能够得到正确答案的关键。
  • 若追问具体区间，可在重启 cur 时更新候选左端点，在刷新 ans 时记录左右端点；主状态无需改变。

易错点总结

  • 将初值设为 0：全负数组 [-2,-1,-3] 会错误返回 0，正确答案是 -1。
  • 转移写成 max(0, cur + nums[i])：这求的是允许空子数组的版本，不符合题意。
  • 最后返回 cur：[4,-1,2,1,-5,4] 的最终 cur 为 5，但历史最优是 6。
  • 从下标 0 再次遍历：首元素会被重复计算，例如 [5] 可能得到 10。
  • 只累加正数：会忽略连续性；[4,-1,2,1] 的答案需要保留中间的负数 -1。

相似题目

题目 难度 考察点
53. 最大子数组和 中等 同一道题的主站版本，可顺带练分治写法
152. 乘积最大子数组 中等 换成乘法后负负得正，需同时维护最大值与最小值两个状态
918. 环形子数组的最大和 中等 数组首尾相接，答案取「普通最大和」与「总和减最小和」较大者
1186. 删除一次得到子数组最大和 中等 允许删一个元素，状态多出「是否已用掉删除机会」一维
1191. K 次串联后最大子数组之和 中等 数组重复 k 次，需按总和正负分类讨论并取模
面试题 16.17. 连续数列 简单 完全同款递推，适合做初次模板复述