CS-Notes 剑指 Offer 42：连续子数组的最大和——单趟贪心算法的推导、实现与边界处理

本篇基于 CS-Notes 仓库中的剑指 Offer 题解文档，系统讲解"连续子数组的最大和"这一经典最大子数组问题：从题目定义出发，完整还原原仓库给出的 O(n) 单趟贪心解法（Kadane 算法）的每一行语义，逐步在示例数组上推演执行过程，并从动态规划角度证明其正确性，最后梳理全负数组、空数组等边界场景的处理要点。读完之后，你能够独立写出该题的 O(n) 时间、O(1) 空间实现，并说清"前缀和一旦非正就必须重置"这一贪心准则背后的数学依据。

1. 问题定义

题解文档给出的原始示例如下（原文见 [notes/42. 连续子数组的最大和.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/42. 连续子数组的最大和.md?utm_source=gitcode_repo_files)）：

{6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。

形式化表述：给定一个整数数组 nums，在下标连续的子数组（subarray）中，找出元素和最大的一个，返回其和。注意三个约束容易被忽略：

• "连续"是硬约束——不能跳着选元素，因此不能退化成"选所有正数之和"；
• 子数组非空，至少要包含一个元素，所以全负数组的答案是最大的那个负数而不是 0；
• 题目要求的是"最大和"本身，经典进阶变体还要求输出子数组的起止下标（本仓库题解仅要求和，下标信息可在遍历中额外维护）。

该题收录于 CS-Notes 的剑指 Offer 题解体系，在 [notes/剑指 Offer 题解 - 目录.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/剑指 Offer 题解 - 目录.md?utm_source=gitcode_repo_files#L92-L103) 的"动态规划"分类下，与斐波那契、礼物的最大价值、最长不含重复字符的子字符串等题并列。原文档同时给出了牛客网对应的练习题链接，可在题解目录顶部找到刷题入口的说明。

2. 核心思路：前缀和一旦非正就"弃前"

原仓库给出的参考实现（完整继承自原文档，未作改动）：

public int FindGreatestSumOfSubArray(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;
    int greatestSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int val : nums) {
        sum = sum <= 0 ? val : sum + val;
        greatestSum = Math.max(greatestSum, sum);
    }
    return greatestSum;
}

这段代码的全部决策浓缩在 sum = sum <= 0 ? val : sum + val; 一行。逐行拆解：

• greatestSum 初始化为 Integer.MIN_VALUE 而不是 0——这是关键细节：它保证当数组元素全为负数时，答案能被更新为"最大的那个负数"，而不是错误地停在 0；
• sum 表示"以当前元素 val 作为右端点的、最优的连续子数组和"。如果走到这一步时它已经 <= 0，说明把它拼接到任何后续子数组上只会拖后腿（贡献非正），那么从 val 重新开始一定更优；
• 每处理一个元素，就用 sum 更新全局最大值 greatestSum，即"以每个位置为右端点的最优和"取全集最大。

贪心准则的正确性可以用反证法说明：假设存在最优子数组 [l..r]，而 nums[l] + ... + nums[l+k] <= 0（前缀非正）。那么 [l+k+1..r] 的和严格不小于 [l..r] 的和，即把非正前缀砍掉不会更差。反复砍除所有非正前缀后，任何最优子数组都可以保证"从其左端点起的前缀和恒为正"，这正是 sum <= 0 就重置、sum > 0 就续接的策略所枚举的空间，因此贪心不会错过最优解。

3. 动态规划视角：原实现就是滚动优化的 DP

把上述准则翻译成 DP 语言，状态定义更清晰：

• 状态：dp[i] = 以 nums[i] 结尾的连续子数组的最大和；
• 转移：dp[i] = max(nums[i], dp[i-1] + nums[i])；
• 答案：max(dp[i])（对全部 i）。

转移的含义与前文一致：要么"从 i 新开一段"，要么"接在 i-1 的最优段后面"。标准写法需要 O(n) 空间：

public int findMaxSubArrayDP(int[] nums) {
    int dp = nums[0];
    int greatestSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        dp = Math.max(nums[i], dp + nums[i]);   // 滚动变量，只依赖上一状态
        greatestSum = Math.max(greatestSum, dp);
    }
    return greatestSum;
}

dp 只依赖前一个状态，滚动成单个变量后空间降为 O(1)——这就是原仓库代码的数学本质：sum 即滚动 dp，greatestSum 即答案。作为对照，朴素做法是枚举所有 O(n²) 个子区间分别求和（O(n³)），或者用前缀和把单次区间和降到 O(1) 从而得到 O(n²)；贪心/Dual 一趟扫描的 O(n) 已是该问题在线性比较模型下的最优量级。

4. 示例数组的逐步推演

用原题目示例 {6, -3, -2, 7, -15, 1, 2, 2} 逐元素执行原实现，验证"最大和为 8（从第 0 个开始，到第 3 个为止）"：

步骤	val	进入时 sum	决策	处理后 sum	greatestSum
1	6	0	sum<=0，重置	6	6
2	-3	6	续接	3	6
3	-2	3	续接	1	6
4	7	1	续接	8	8
5	-15	8	续接	-7	8
6	1	-7	sum<=0，重置	1	8
7	2	1	续接	3	8
8	2	3	续接	5	8

可以看到两次"重置"时刻：第 5 个元素把累计和打到 -7 后，第 6 个元素 1 触发了 sum <= 0 ? val : sum + val 中的重置分支；最终最大值 8 产生于下标 0~3 的区间 [6, -3, -2, 7]，与题目描述完全吻合。

5. 边界场景与正确性细节

• 全负数组，如 {-3, -2, -5}：每个位置都会触发重置，greatestSum 依次被更新为 -3、-2，最终返回 -2（最大的单个负数）。若把 greatestSum 错误初始化为 0，这里就会返回 0，与"子数组非空"的语义矛盾——原实现用 Integer.MIN_VALUE 精确规避了这一点；
• 空数组 / null 输入：原实现约定返回 0，属于接口层面的防御性处理，避免解引用异常；
• 含 0 的数组：sum <= 0 与 sum < 0 两种写法都能得到正确答案。选 <= 0 时，值为 0 的前缀会被视为"无益前缀"而弃掉，语义上更干净（前缀贡献为 0 时续接与重置等价，但重置避免了无谓的依赖）；
• 单元素数组：循环执行一次，直接返回该元素，无需特判。

6. 仓库内的同思路题解与延伸

CS-Notes 的题解体系对这道题的定位是"动态规划"（见 [notes/剑指 Offer 题解 - 目录.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/剑指 Offer 题解 - 目录.md?utm_source=gitcode_repo_files#L92-L103)），其分类下同批题目如 [notes/10.1 斐波那契数列.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/10.1 斐波那契数列.md?utm_source=gitcode_repo_files)、[notes/47. 礼物的最大价值.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/47. 礼物的最大价值.md?utm_source=gitcode_repo_files)、[notes/49. 丑数.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/49. 丑数.md?utm_source=gitcode_repo_files)、[notes/60. n 个骰子的点数.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/60. n 个骰子的点数.md?utm_source=gitcode_repo_files) 都是"状态 + 转移"的标准 DP 训练，可与本文的滚动 DP 对照阅读。

更重要的是，仓库里有两道题与本题共享"单趟扫描 + 维护一个滚动状态变量"的骨架，值得对比掌握：

• [notes/63. 股票的最大利润.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/63. 股票的最大利润.md?utm_source=gitcode_repo_files)：同样是一次遍历，但滚动状态是"迄今为止的最低买入价" soFarMin，每次尝试以当前价为卖出价计算收益并取最大——与本题"滚动最优前缀和 vs 当前最优全局和"的双变量结构几乎同构；
• [notes/59. 滑动窗口的最大值.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/59. 滑动窗口的最大值.md?utm_source=gitcode_repo_files)：同样是数组扫描问题，但它把窗口约束显式化，用大顶堆维护窗口内最大值，时间复杂度 O(N log M)——可作为"当 O(n) 贪心不可用时引入辅助数据结构"的对照样本。

7. 复杂度总结

以数组长度为 n 计，原实现的复杂度为：

指标	数值	说明
时间	O(n)	单次遍历，每元素 O(1)
空间	O(1)	仅 sum、greatestSum 两个标量（滚动 DP）

面试作答时的完整脉络可以概括为三句话：定义"以 i 结尾的最优和"这一状态 → 推出 max(nums[i], dp[i-1]+nums[i]) 的转移并说明其贪心依据（非正前缀必弃）→ 指出滚动优化后 O(n) 时间、O(1) 空间，并用 Integer.MIN_VALUE 初始化正确处理全负边界。这套论证结构直接来自 [notes/42. 连续子数组的最大和.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/42. 连续子数组的最大和.md?utm_source=gitcode_repo_files) 的参考代码，本文仅在此基础上补齐了推导过程、逐元素验证与复杂度对照，可作为该题解的加深版阅读。