做了这么多年技术面试过不少候选人也带过不少新人有一个算法题几乎每次聊到动态规划都会绕不开——最大连续子序列和。LeetCode上叫Maximum Subarray剑指Offer里是第42题各平台的高频题榜单里常年有它。这道题有意思的地方在于代码写起来可能连十行都不到但能把这个题讲明白的人往往对动态规划的本质理解得很透彻。我见过不少候选人在黑板上哼哧哼哧写出了标准解法一问“dp数组为什么这么定义”立马卡壳。别小看这一问它能牵出整个动态规划思维模式的底层逻辑。接下来的内容我会从拿到题目怎么分析开始一路讲到状态定义、转移方程、代码实现、空间优化、变种题型以及实际场景里的应用。全程跟着我的思路走一遍之后你会发现在这道题的背后其实藏着一套解决“连续型序列问题”的通用方法论。1. 把题目读懂比急着写代码更重要1.1 题目到底在说什么题目描述很简短给定一个整数数组 nums找到一个具有最大和的连续子序列子数组返回其最大和。这里的几个关键词值得先掰扯清楚。第一个是“连续”。连续意味着你不能跳着选元素。比如数组 [1, -2, 3, 4]你可以选 [3, 4]但不能选 [1, 3, 4]因为 1 和 3 之间隔了一个 -2选出来就不是原数组的连续片段了。第二个是“子序列”。在很多算法教材里“子序列”不要求连续“子数组”或“子串”才要求连续。但在这道题的语境下我们讨论的是连续的版本也就是 substring / subarray 的概念。所以如果你在面试时听到“最大连续子序列”可以直接看成“最大子数组和”不要被名词绕晕。第三个是“和最大”。这个“最大”是全局最大不一定以数组末尾结尾这也是后面代码里为什么需要维护一个全局答案而不是直接返回 dp 最后一个值的原因。1.2 暴力解法为什么撑不住没有系统学过动态规划的人第一反应往往是暴力。枚举所有可能的起点 i 和终点 j计算从 i 到 j 的和然后取最大。三层循环可以直接做到 O(n^3)稍微优化一下枚举起点后用累加的方式滚动求和能压到 O(n^2)但还是不够。我经常用一个生活例子来解释这个复杂度差距假设你有 10 万条交易数据想找出最大盈利区间O(n^2)意味着最多要跑 100 亿次运算在常规机器上得几十秒到几分钟。而用动态规划的 O(n) 解法一次遍历就能出结果连 1 毫秒都用不到。暴力解法的真正问题在于它把大量区间重复求和的中间结果浪费了。比如算区间 [2, 5] 的和其实可以在算区间 [2, 4] 的基础上加一个 nums[5]但暴力枚举的思路不会刻意去复用这些结果。这恰恰是动态规划的切入点——把子问题的结果存下来供后续决策使用。1.3 拿到题后的两个灵魂拷问我自己的做题习惯是看到这种“最优化”问题先问自己两个问题。第一个问题子问题能不能拆对于最大连续子序列来说一个长度为 n 的问题能不能借助长度为 n-1 的问题推导出来如果 A 是某个以第 i 个元素结尾的最优解那么它能怎么帮助计算以第 i1 个元素结尾的最优解这个问题的答案直接指向状态转移方程。第二个问题无后效性是否满足所谓无后效性就是过去的状态不会影响未来的决策未来只关心当前状态的值而不关心这个值是怎么来的。对于这道题如果我知道了以第 i 个元素结尾的最大和是 5那我去算第 i1 个元素结尾的最大和时只需要这个 5至于这 5 是从哪个起点开始累加的完全不重要。这就是无后效性的体现。这两个问题想通了状态定义就是水到渠成的事。2. DP状态设计最大的坑其实在定义上2.1 一个经典错误把dp[i]定义成“前i个元素的最大子序列和”很多初学者会试着把 dp[i] 定义为“数组前 i 个元素里最大连续子序列的和”。这个定义听起来很自然但走到转移方程时就会发现完全走不动。因为最大子序列可能以任意位置结尾你知道了前 i-1 个元素的最大和怎么推出前 i 个元素的最大和没法推。要么新子序列包含第 i 个元素要么不包含但如果不包含第 i 个元素根本不知道之前的最大子序列结尾在哪里、值是多少也就无法判断加上第 i 个元素后是赚了还是亏了。我自己的经验是对于连续区间类的问题只要看到“连续”“子数组”“子串”这些限定词状态定义十有八九要落在“以某个位置结尾”上。这几乎成了肌肉记忆。原因也简单只有强制规定了子序列的结尾位置才能在尾部延伸出一个新的元素形成递推关系。2.2 正确的状态定义与转移方程推导正确的状态定义是dp[i] 表示以 nums[i] 这个元素作为结尾的连续子序列其最大和是多少。注意这里的关键点必须包含 nums[i]而且必须以 nums[i] 结尾。这样一来dp[i] 的候选值就只有两个来源。第一种把 nums[i] 接在 dp[i-1] 对应的那个子序列后面。如果 dp[i-1] 是正的说明前面那趟累加在帮我们赚更多接上去肯定比单独拿 nums[i] 更大。第二种直接抛弃前面的所有累加结果从 nums[i] 重新开始。如果 dp[i-1] 是负的说明再接上去只会拖累整体和这时候断臂求生才是最优选择。所以转移方程就出来了dp[i] max(dp[i-1] nums[i], nums[i])这也是 Kadane 算法的核心公式。很多人会觉得“负的就丢弃”这个规则太简单但它其实精妙得很。它隐式地处理了子序列的起点问题每当 dp[i-1] 为负时子序列的起点就从 i 重新开始。从这个角度看遍历过程中我们其实是在不断尝试“换起点”和“保持起点”之间的最优权衡而不是真的去记录起点在哪。2.3 最终答案为什么不是dp[n-1]状态定义决定了 dp[n-1] 仅仅是“以最后一个元素结尾”的最大连续子序列和。但整个数组的最大连续子序列完全可能结束在中间某个位置。比如数组 [3, -10, 100]以第三个元素 100 结尾的子序列和是 100整个数组最大值是 100但如果是 [5, -1, -2, 10]以最后一个元素 10 结尾的最大子序列是 10而真正的最大子序列是 [5, -1, -2, 10]整体和是 12这就大于 dp[3] 吗其实不是因为以最后一个元素 10 结尾的最大子序列包含前面所有元素时和是 12所以 dp[3] 也是 12。但为了保险我们需要再想一个例子比如 [1, -2, 3]以最后一个元素 3 结尾的最大子是 3全局最大也是 3貌似一致。那有没有 dp[n-1] 不等于全局最大值的情况有比如 [3, -2, 5, -100]以最后一个元素 -100 结尾的最大子序列和是 -100但全局最大是 [3, -2, 5] 6。所以答案是遍历过程中维护一个 best随时更新为 max(best, dp[i])而不是傻傻地取 dp 的最后一个值。这个细节是很多第一次写这道题的选手最容易翻车的地方。3. 从朴素DP到滚动变量代码怎么一步步写出来3.1 朴素动态规划版本先给出一个最容易理解的版本用完整 dp 数组保存所有中间状态。我用 Python 写一个示例def max_subarray_sum(nums): n len(nums) if n 0: return 0 dp [0] * n dp[0] nums[0] best nums[0] for i in range(1, n): dp[i] max(dp[i - 1] nums[i], nums[i]) best max(best, dp[i]) return best这个版本的优点是直观每一个 dp[i] 都表示以 i 结尾的最大子序列和调试时可以把 dp 数组打出来看变化过程特别适合学习阶段。看一个具体例子数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]i0, nums[0]-2, dp[0]-2, best-2 i1, nums[1]1, dp[1]max(-21, 1)1, best1 i2, nums[2]-3, dp[2]max(1-3, -3)-2, best1 i3, nums[3]4, dp[3]max(-24, 4)4, best4 i4, nums[4]-1, dp[4]max(4-1, -1)3, best4 i5, nums[5]2, dp[5]max(32, 2)5, best5 i6, nums[6]1, dp[6]max(51, 1)6, best6 i7, nums[7]-5, dp[7]max(6-5, -5)1, best6 i8, nums[8]4, dp[8]max(14, 4)5, best6最终结果是 6对应的子序列是 [4, -1, 2, 1]和确实是 6。在整个推导过程中可以看到当 dp[i-1] 为负数时比如 i2 时 dp[2] -2等 i3 时直接抛弃了前面的累加结果从 4 重新开始。这就是“断臂求生”的实际含义。3.2 滚动变量从O(n)空间到O(1)空间在做题和实际开发中保存整个 dp 数组往往是没有必要的因为 dp[i] 只依赖 dp[i-1]。这是一个非常典型的“仅依赖前一项”的递推关系完全可以用两个变量滚动更新。优化后的代码也简单def max_subarray_sum(nums): cur nums[0] best nums[0] for x in nums[1:]: cur max(x, cur x) best max(best, cur) return best这个版本就是经典的单层循环 Kadane 算法时间复杂度 O(n)空间复杂度 O(1)。代码只有四行核心逻辑。我见过有些面试者会觉得这个版本是偷机取巧或者“背答案”其实不是。它就是利用滚动变量消除冗余空间的常规操作和斐波那契数列用两个变量滚动代替整个数组是同一个思想。真正理解朴素版本之后优化版自然就出来了不建议直接背优化版代码否则一个变种题就能把你打回原形。3.3 其他语言的实现C 版本的写法也很常见面试时写这个更符合多数公司的技术栈int maxSubArray(vectorint nums) { if (nums.empty()) return 0; int cur nums[0]; int best nums[0]; for (int i 1; i nums.size(); i) { cur max(nums[i], cur nums[i]); best max(best, cur); } return best; }如果面试官问了边界情况比如“数组为空时返回什么”这里的处理是返回 0。但不同题目定义里可能要求不同有的要求返回 INT_MIN有的要求抛异常尽量先问清楚再动手。如果题目没说空数组通常默认 n 1那 cur 直接初始化为 nums[0] 就不会有问题。4. 边界条件与常见误区每一个都能写成一份面经4.1 全负数数组怎么处理我拿这个题面试过很多人发现最容易纠结的就是“数组全为负数”的场景。比如 [-3, -5, -1, -4]正确答案应该是 -1也就是选一个最大的负数。但有些第一版代码会在循环里加一句“if cur 0 then cur 0”这本是求“最大非负和”的思路用在答案必须 0 的问题上没问题但用在允许负数的原始题目上就会挂掉。正确做法是一开始就把 cur 和 best 都初始化为数组的第一个元素然后从第二个元素开始递推。这样当全负数时cur max(nums[i], cur nums[i]) 的结果就是在“从当前元素重新开始”和“接上前面一段可能更负的和”中选最大的最终 cur 总是保持从当前位置往前连续子序列里的最大和即使它是负数best 也会记录下最大的那个负数。这里有一个经验初始化不能用 0而要用数组第一个元素。用 0 初始化的后果是全负数数组要么返回 0 这种错误答案要么需要额外打补丁特判。很多初学者的代码就是在这里翻车的。4.2 “只取正数再累加”的陷阱有人会想既然要找最大和那我只挑正数不就行了不行因为“连续”这个限制是硬约束。考虑 [8, -2, 5] 这个例子如果只取正数那最大和是 13但 8 和 5 不连续中间隔了 -2。实际子序列 [8, -2, 5] 的和是 11这才是正确答案。所以必须容忍那些“小的负数”因为它们是实现连续性的“桥梁”。如何判断一个负数能不能忍关键就看它接上前面的子序列后总体值是不是还大于从它本身重新开始的值。状态转移方程做的就是这件事。4.3 关于空数组和溢出问题有些题目会给出空数组的用例这时候需要直接返回 0 或者题目约定的最小值。但如果约定 n 1就不用特判。我个人习惯先写防御式代码开头加一个“if nums 为空”的分支因为在实际生产环境里你很难保证输入数据不会为空。另一个容易忽视的点是整数溢出。如果数组元素很大、长度很长累加和可能超出 int 范围。像 C 里 int 是 32 位的最大只能表示约 21 亿如果数组里有十几亿级别的数连续加上几次就会溢出。面试时可以跟面试官确认数值范围或者直接改用 long long。刷题网站一般不会用极端大数据卡这个但真实业务里的数据没法保证思想上要有防溢出的意识。5. 进阶问题光求最大值不够我还想要子序列本身5.1 用起点和终点记录区间很多时候面试官会在你背完 Kadane 之后随即追加一个要求不仅返回最大和还要返回对应的连续子序列。例如输入 [-2, 1, -3, 4, -1, 2, 1, -5, 4]最大和是 6子序列是 [4, -1, 2, 1]这时候下标区间是 [3, 6]。如果再要求返回起止下标又该怎么改思路很简单在滚动过程中用变量记录当前的左端点 start 和右端点 end每次更新 cur 时如果决定“从 x 重新开始”那么临时起点就跳到当前位置如果决定“接上前面的 cur”临时起点保持不变。每次 best 被刷新时就把当前的临时起点和当前位置记为最终答案的起止点。5.2 代码实现记录起止点版本直接上代码def max_subarray_with_index(nums): if not nums: return 0, -1, -1 cur nums[0] best nums[0] temp_start 0 start 0 end 0 for i in range(1, len(nums)): if cur nums[i] nums[i]: cur cur nums[i] else: cur nums[i] temp_start i if cur best: best cur start temp_start end i return best, start, end核心变化就一句话当 cur nums[i] 比 nums[i] 小的时候意味着前面的累加是负收益我们选择从 nums[i] 重新开始所以临时起点更新为 i否则继续接上。只有当 cur 刷新了 best 的时候才把临时起点和当前终点写入最终结果。这个变体在真实业务里很有用因为知道最大和本身的价值往往不如知道哪段时间区间贡献了这个最大值。比如在监控系统里找到了最大流量连续上涨的区间就能定位到对应的日志或者指标时间段。5.3 变体一最大连续子序列乘积还有一道同样高频的变体题求最大连续子序列乘积。比如 [2, 3, -2, 4]最大乘积是 2×36。表面看起来比求和复杂因为负数乘以负数会变正数导致你不能只维护一个最大值。解决方法是同时维护两个状态当前乘积最大值 curMax 和当前乘积最小值 curMin。因为最小值可能是负数乘以一个负数后反而会变成最大值。def max_product(nums): if not nums: return 0 cur_min nums[0] cur_max nums[0] best nums[0] for x in nums[1:]: candidates (x, cur_max * x, cur_min * x) cur_max max(candidates) cur_min min(candidates) best max(best, cur_max) return best这道题其实是最大连续子序列和的直接扩展。理解清楚了“为什么状态定义要加上结尾位置”这一点就能自然理解乘积变体为什么需要维护两个值。5.4 变体二环形数组上的最大连续子序列和如果题目把数组改成上是首尾相连的环形数组比如 [5, -3, 5]线性数组的最大子序列和是 7但环形数组里还可以跨过首尾取 [5, 5] 的和是 10这就更大了。解法是求“最大值”和“最小值”两个答案取大的思路环形数组的最大子序列和要么在数组内部不跨越边界要么跨越边界等价于总和减去最小子序列和。所以可以写两次 Kadane一次求最大子序列和一次求最小子序列和两者取 max再加上特判“全部为负数”的情况。这里先不展开代码因为单列出来又能写一整篇文章但思路值得记住。6. 这类DP思路在真实场景中能做什么6.1 股票买卖的最大单次收益以股票为例如果你只能买卖一次那本质上就是找最小的买入价和之后最大的卖出价之间的价差。把相邻两天的价格差做成一个差分数组最大收益就是“差分数组的最大连续子序列和”。比如每日价格 [100, 80, 120, 130, 70]差分是 [-20, 40, 10, -60]最大连续子序列和是 50对应 80 买入、130 卖出。我实际做过类似的数据分析业务从行情数据接口拿几千只股票的历史价格用 Kadane 算法批量算每只股票在某段时间里的最大涨幅区间单次遍历就能跑完性能完全不是瓶颈。这比写一堆 pandas 条件筛选要清爽得多。6.2 监控告警与异常区间定位在运维监控场景里经常要看一段连续时间段里的指标变化。比如某一台服务器的网络流量在一连串的时间点上出现了持续上涨你希望自动识别出上涨最猛的那一段方便回溯是不是有异常任务在跑。把流量数据取出来后对每相邻两个时间点计算差值再用最大连续子序列算法找出累计上涨最大的时间窗口比人工盯着图表找要高效得多。实际业务里我处理过类似问题一个接口的访问延迟数据在某个版本发布后连续多天爬升靠这算法一键定位到了异常窗口再结合发布记录分钟级就找到了原因。6.3 图像处理和其他信号处理领域的小尝试在图像处理中求最大子矩形和这类问题也可以先压缩行或列转化为一维的最大连续子序列和问题再求解这是经典的降维手段。虽然听起来有点远但它说明了一个道理算法题的模型一旦吃透迁移到真实业务里只是改个壳的事。6.4 为什么说状态定义是动态规划的魂我做了这么多年技术也带过不少新人入门算法最大体会是看不懂动态规划百分之七十是卡在状态定义上。状态定义包含了这个问题最本质的结构信息定义好了转移方程其实是一步步推理的结果定义不好背再多代码也没用。最大连续子序列和就是一个绝佳的入门题它规模小、形式简单但完整展示了“定义状态 - 推导转移 - 空间优化 - 变体迁移”的思考过程。把这一题的思路吃透后面再看背包、LIS、编辑距离这些经典DP思维路径都是相似的。7. 给后来者的一点建议如果让我从这道题里提炼出最值得记住的一条经验那就是遇到“连续子数组/子序列”相关的最值问题优先考虑“以每个位置结尾作为状态”这个套路。它像一个万能钥匙可以直接打开一大类问题。第二个建议是别急着写优化版。我见过很多刷题选手上来就背 Kadane 算法的四行代码结果问到怎么输出子序列就懵了问到为什么 cur 要为 0 还是 nums[0] 也说不清。先老老实实写 dp 数组版本把每一步递推过程在纸上推演一遍再随手优化成滚动变量版本这样形成的记忆才是牢固的。第三个建议是多想想变体。最大连续子序列和、最大连续子序列乘积、输出起止下标、环形数组版本、二维矩阵最大子矩阵和。每想一个变体你就对原问题多一层理解。等到面试时面试官从主问题拐到变体你能快速迁移那这道题才算真正过关。最后分享一个我实际调试时的小技巧。如果你不确定自己的 Kadane 算法写的对不对拿一个全正数数组试一下应该返回整个数组的和再拿一个全负数数组试一下应该返回最大的那个负数再拿一个类似 [-1, 2, 3, -2, 5] 的混合数组自己手算一遍再跑代码。这三个测试用例能过滤掉绝大多数实现错误。我至今写这一类题都会在脑内先过一遍这三个例子算是多年养成的习惯。