LeetCode 面试题 16.17. 连续数列 | 走在修行的大街上

走在修行的大街上

2026-03-28 HGNULB 约 11 分钟

文章信息 3 个分类 3 个标签

分类

LeetCode 简单程序员面试金典（第 6 版）

目录

题目描述

✅ 面试题 16.17. 连续数列

题意分析

给定整数数组 nums，找出一个非空连续子数组使其元素和最大，返回这个和。

三个词决定了全部设计。「连续」意味着答案是一段区间，于是每个位置只面临二选一：接在前面那段后面，或者从自己重新开一段。「非空」意味着必须选至少一个元素——数组可能全是负数（如 [-2,-1]，答案是 -1），所以答案的初值绝不能是 0，否则会返回空子数组的和。「最大」则要求在所有右端点上取全局最优。

暴力枚举所有区间是 $O(n^2)$。优化的入手点是找一个能递推的状态。直接定义「前 i 个元素中的最大子数组和」是行不通的——知道了前 i 个的答案，无法推出前 i+1 个的答案，因为新元素能否接上取决于那段最优子数组是否恰好在位置 i 结束，而这个信息被丢掉了。

正确的状态定义要加上「以当前位置结尾」这个约束：cur = 必须以 nums[i] 结尾的最大连续和。约束反而让递推成立了，因为「以 i+1 结尾」的段一定包含 nums[i+1]，它要么紧接在「以 i 结尾」的最优段后面，要么单独成段。这是本题最核心的一步，也是动态规划里「把状态定得更窄反而更好推」的经典范例。

全局答案则在每个位置用 cur 刷新一次——因为最大子数组可以在任意位置结束，遍历所有结束位置就覆盖了所有可能。

解法一：动态规划滚动变量

核心思路

定义 cur 为「必须以当前元素结尾的最大连续和」，ans 为全局最大值。

递推只有两个候选：cur + nums[i]（接上前面那段）与 nums[i]（自己重新开始），取较大者。这个式子还可以进一步简化——比较 cur + nums[i] 与 nums[i] 等价于比较 cur 与 0，所以判断条件可以写成：若 cur < 0 就丢弃前面重新开始，否则累加。两种写法完全等价，后者更能说明「为什么」：前缀和为负时，它对后面的任何段都只有拖累，理应整段丢弃。

因为递推只依赖上一个位置的 cur，不需要开数组，一个滚动变量就够，空间降到 $O(1)$。这就是 Kadane 算法。

正确性依赖不变量：每轮结束时 cur 是以当前下标结尾的最优和，ans 是所有已处理结束位置上的最大值。归纳来看，「以 i 结尾的最优段」去掉 nums[i] 后必然是「以 i-1 结尾的某个段」，而在所有这类段中最优的就是上一轮的 cur，所以取 max(cur, 0) + nums[i] 不会漏掉更优解。

初始化用 cur = ans = nums[0]，遍历从下标 1 开始。这样既满足了「非空」的要求，也天然覆盖了全负数组——全负时每轮都会重新开段，ans 最终等于数组里的最大元素。

解题步骤

初始化：cur = nums[0]、ans = nums[0]。关键是不要初始化为 0；用首元素初始化同时解决了「非空」和「全负数组」两个问题。

从下标 1 开始遍历（下标 0 已在初始化时消费掉了，重复处理会让首元素被算两次）。

递推 cur：若 cur < 0 则 cur = nums[i]（丢弃负贡献的前缀），否则 cur += nums[i]。

刷新 ans：ans = max(ans, cur)。必须在 cur 更新之后做，比较的是「以当前位置结尾的最优值」。

返回 ans，而不是 cur——cur 只是最后一个位置的局部值。

以官方样例 nums = [-2,1,-3,4,-1,2,1,-5,4] 走一遍：

初始 cur = ans = -2。
i=1（值 1）：cur = -2 < 0 → 重开，cur = 1；ans = max(-2, 1) = 1。
i=2（值 -3）：cur = 1 >= 0 → 累加，cur = -2；ans 保持 1。
i=3（值 4）：cur = -2 < 0 → 重开，cur = 4；ans = 4。
i=4（值 -1）：累加，cur = 3；ans 保持 4。
i=5（值 2）：累加，cur = 5；ans = 5。
i=6（值 1）：累加，cur = 6；ans = 6。
i=7（值 -5）：累加，cur = 1；ans 保持 6。
i=8（值 4）：cur = 1 >= 0 → 累加，cur = 5；ans 保持 6。

返回 6，对应子数组 [4,-1,2,1]，与期望一致。注意 i=7 那一步：cur 从 6 掉到 1，但因为仍非负所以没有重开，而正是这个保留让 i=8 能累加到 5——虽然本例没超过 6，但这说明「只在 cur < 0 时重开」比「一变小就重开」是必要的。

再看全负用例 nums = [-2,-1]：初始 cur = ans = -2；i=1 时 cur = -2 < 0 重开为 -1，ans = max(-2,-1) = -1。返回 -1，正确。若把 ans 初始化为 0，会错答成 0。

代码实现

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

        for (int i = 1; i < nums.length; i++) {
            // cur 表示必须以当前位置结尾的最大连续和。
            if (cur < 0) {
                cur = nums[i];
            } else {
                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++ {
        // cur 表示必须以当前位置结尾的最大连续和。
        if cur < 0 {
            cur = nums[i]
        } else {
            cur += nums[i]
        }
        if cur > ans {
            ans = cur
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，单次扫描，循环体内只有常数次比较与加法。

空间复杂度：$O(1)$。虽然是动态规划，但状态只依赖前一格，滚动成两个变量即可，不需要 dp 数组。

关键点总结

状态必须定义为「必须以当前元素结尾的最大连续和」。去掉这个约束，递推关系就不成立——这是本题最值得记住的一课。

cur < 0 就重开，本质是「负前缀对后续只有拖累」；这与 max(cur + nums[i], nums[i]) 完全等价，但更能解释原因。

ans 与 cur 是两个不同的量：cur 是局部（以当前位置结尾），ans 是全局（所有结束位置的最优）。返回的必须是 ans。

用 nums[0] 初始化而非 0，一步同时满足「非空」与「全负数组」。

遍历从下标 1 开始，避免首元素被重复计入。

解法二：前缀和 + 历史最小前缀

核心思路

换一个视角：子数组 [l, r] 的和等于 prefix[r+1] - prefix[l]。固定右端点后，要让这个差最大，就要让减去的 prefix[l] 尽可能小。

于是从左到右扫描，维护当前前缀和 prefixSum 与它之前出现过的最小前缀和 minPrefixSum，每一步用 prefixSum - minPrefixSum 更新答案。

两个细节保证了正确性。第一，minPrefixSum 初始化为 0，代表空前缀 prefix[0] = 0，这样以下标 0 开头的子数组也能被覆盖。第二，必须先用当前前缀更新答案，再把当前前缀并入 minPrefixSum。如果顺序颠倒，minPrefixSum 可能就是 prefixSum 自己，相减得 0，等于允许了空子数组，与「非空」要求冲突。

这个视角的价值在于可迁移：它和 121 题「买卖股票的最佳时机」是同一个模型（当前价格减历史最低价），也是 560「和为 K 的子数组」那类前缀和加哈希题的同源思路。本题本身用 Kadane 更直接，但掌握这个转换能打通一整类子数组问题。

解题步骤

初始化：prefixSum = 0、minPrefixSum = 0（空前缀）、ans = nums[0]。ans 仍不能取 0。

遍历每个元素：prefixSum += num。

先更新答案：ans = max(ans, prefixSum - minPrefixSum)。此刻 minPrefixSum 来自严格更早的前缀，保证子数组非空。

后更新最小前缀：minPrefixSum = min(minPrefixSum, prefixSum)，供后续位置使用。

返回 ans。

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 走一遍（列出每步的 prefixSum / minPrefixSum / ans）：

初始 0 / 0 / -2。
加 -2：prefixSum = -2，ans = max(-2, -2-0) = -2，minPrefixSum = -2。
加 1：-1，ans = max(-2, -1-(-2)) = 1，minPrefixSum 保持 -2。
加 -3：-4，ans = max(1, -4-(-2)) = 1，minPrefixSum = -4。
加 4：0，ans = max(1, 0-(-4)) = 4，minPrefixSum 保持 -4。
加 -1：-1，ans = max(4, 3) = 4。
加 2：1，ans = max(4, 5) = 5。
加 1：2，ans = max(5, 6) = 6。
加 -5：-3，ans = max(6, 1) = 6。
加 4：1，ans = max(6, 5) = 6。

返回 6，与 Kadane 一致。最优解出现在 prefixSum = 2、minPrefixSum = -4 处，对应的正是 [4,-1,2,1] 这段。

再看 nums = [-1]：prefixSum = -1，ans = max(-1, -1-0) = -1，正确。若把「更新最小前缀」提到「更新答案」之前，minPrefixSum 会先变成 -1，ans = max(-1, 0) = 0，错答成 0——这正是顺序不能颠倒的证明。

代码实现

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

        for (int num : nums) {
            prefixSum += num;
            // 当前前缀减去此前最小前缀，就是以当前位置为右端点的最优和。
            ans = Math.max(ans, prefixSum - minPrefixSum);
            minPrefixSum = Math.min(minPrefixSum, prefixSum);
        }

        return ans;
    }
}

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

    for _, num := range nums {
        prefixSum += num
        // 当前前缀减去此前最小前缀，就是以当前位置为右端点的最优和。
        if prefixSum-minPrefixSum > ans {
            ans = prefixSum - minPrefixSum
        }
        if prefixSum < minPrefixSum {
            minPrefixSum = prefixSum
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，每个元素处理一次。

空间复杂度：$O(1)$，不需要显式的前缀和数组，滚动两个变量即可。

关键点总结

子数组和 = 两个前缀和之差，固定右端点后要减去历史最小前缀，这是所有子数组求和类问题的通用入口。

minPrefixSum 初值取 0（空前缀），才能覆盖以下标 0 开头的子数组。

「先更答案、再更最小前缀」保证减去的前缀严格更早，从而子数组非空。[-1] 是检验这一点的最短用例。

这个模型与 121 股票题、560 子数组和为 K 同源，值得作为一类来记。

解法对比

Kadane 滚动变量：$O(n)$ 时间、$O(1)$ 空间。状态定义直接对应题意，代码只有几行，边界仅需注意初值，是面试首选。

前缀和 + 历史最小前缀：同样 $O(n)$ / $O(1)$。本题上并不比 Kadane 更优，价值在于它揭示了「区间和 = 前缀差」这个更通用的框架——遇到「和为 K 的子数组」「和可被 K 整除」「最长和为 K 的子数组」时，Kadane 无从下手，而这个框架直接可用。

另外值得知道本题还有分治解法（对应 tags 里的「分治」）：递归求左半最大、右半最大、跨中点最大三者取最优，时间 $O(n \log n)$。它比两个线性解法都慢，但它是线段树维护区间最大子段和的基础，也是面试官偶尔追问「如果要支持单点修改并多次查询呢」时的正解方向。

面试建议：先写 Kadane 并把「以当前位置结尾」这个状态定义讲清楚（面试官真正想听的是这句），再补一句前缀和视角以展示题型迁移能力。

易错点总结

ans 初始化为 0：全负数组会错答成 0。[-2,-1] 正确答案是 -1，[-1] 是 -1。这是本题第一大错误。

把 cur 当成全局答案返回：cur 只是「以最后一个元素结尾」的值。[1,-1] 会返回 0 而正确答案是 1。

状态定义漏掉「以当前位置结尾」：定义成「前 i 个的最大子数组和」会发现递推写不出来，硬写就会漏解。

遍历从下标 0 开始：首元素在初始化时已计入，再处理一次会让 cur 变成 2 * nums[0]。

cur 更新前就刷新 ans：比较的是上一轮的局部值，答案会滞后一位。

重开条件写成「cur 变小就重开」：只有 cur < 0 才该丢弃。[4,-1,2,1] 里 -1 让 cur 变小但仍应保留，错误条件会把答案切成 4。

前缀和写法把顺序颠倒：先更新 minPrefixSum 再更新答案，会把空子数组计入。[-1] 会错答成 0。

minPrefixSum 初值不取 0：以下标 0 开头的子数组无法被统计到。

误以为可以用滑动窗口：数组含负数，窗口和不单调，收缩左边界没有依据。

整型溢出的顾虑：本题元素范围与长度使得和落在 int 内，不必换 64 位；但把这套代码迁移到元素范围更大的题目时要留意。

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	与解法二同一模型：当前值减历史最小值
152. 乘积最大子数组	中等	改成乘积后负负得正，需同时维护以当前结尾的最大值与最小值
918. 环形子数组的最大和	中等	环形数组，用「总和减最小子数组和」处理跨界情形，注意全负特判
560. 和为 K 的子数组	中等	前缀和加哈希，展示解法二框架在「求个数」场景下的延伸
1186. 删除一次得到子数组最大和	中等	Kadane 加一维状态，记录「是否已使用删除机会」
1191. K 次串联后最大子数组之和	中等	数组重复 K 次，需分类讨论总和正负并结合前后缀最大和
剑指 Offer 42. 连续子数组的最大和	简单	与本题同题，可直接套用