开篇先聊点实在的。动态规划DP求最大连续子序列和这个标题看着像教科书目录但它其实是算法面试里出场率最高的几个基础题之一也是很多人第一次真正“理解DP为什么好用”的入口。题面很简单给你一个整数数组里面可能有负数让你找出一个连续的子数组使它的和最大输出这个最大和就行。很多入门教程喜欢直接甩一个状态转移方程dp[i] max(dp[i-1] nums[i], nums[i])然后告诉你“这就是答案”。但真到了面试或者实际工程里你会发现更大的价值在于为什么状态要这么定义为什么不能用滑动窗口如果题目让你输出那个子数组本身怎么办如果是环形数组怎么办二维矩阵怎么办这一串问题追下来才能真正把一个经典题吃透。这篇文章我不打算只贴解法。我会从最原始的暴力思路讲起一步步推导出DP状态设计的过程再给出完整可运行的代码、复杂度分析、常见变形和面试实战技巧。不管你是刚入门算法的学生还是准备跳槽刷题的开发者这篇都值得完整过一遍。1. 问题本质与暴力解法的局限1.1 题目到底在问什么先明确一下输入输出。给定一个整数序列nums例如[-2, 1, -3, 4, -1, 2, 1, -5, 4]要求找到一个连续的子数组比如[4, -1, 2, 1]它的和是6这是整个数组中所有连续子数组里和最大的一个所以输出6。有个关键细节容易被忽略“连续”两个字。这意味着你不能跳着选元素子数组在原数组中的位置必须是连在一起的。这也就决定了这个问题没法用简单的排序或者贪心解决因为一旦排序连续性就完全被破坏了。另一个容易踩坑的地方是题目没有说数组里全是正数。如果全是正数那整个数组的和就是答案这事儿没有讨论价值。正是因为有负数存在问题才变得有意思——你必须在“往前扩展”和“重新开始”之间做抉择。比如[4, -1, 2, 1]这个子数组中间那个-1并没有拖垮整体但如果你遇到-5之后还硬要把它加进来可能就不如直接从下一个正数重新开始了。1.2 暴力枚举为什么不可行我先带你走一遍最直观的暴力思路。枚举所有可能的起点i和终点j直接计算i到j之间的和维护一个最大值。这样做的代码很简单三层循环就能搞定def max_subarray_brute(nums): n len(nums) max_sum float(-inf) for i in range(n): for j in range(i, n): cur 0 for k in range(i, j 1): cur nums[k] max_sum max(max_sum, cur) return max_sum这个解法的时间复杂度是 O(n³)n 稍微大一点就完全跑不动。稍微优化一下去掉最内层循环用累加的方式在枚举终点时同步维护当前和def max_subarray_brute_opt(nums): n len(nums) max_sum float(-inf) for i in range(n): cur 0 for j in range(i, n): cur nums[j] max_sum max(max_sum, cur) return max_sum这样时间复杂度降到 O(n²)空间复杂度 O(1)。看起来不错了但当 n 达到 10⁵ 甚至 10⁶ 时O(n²) 依然是天文数字。10⁵ 的平方是 10¹⁰按每秒 10⁸ 次基本运算估算需要 100 秒这在任何在线评测系统里都是不可接受的。所以这个问题真正的目标是寻找 O(n) 甚至 O(n log n) 的解法。这也是为什么它适合作为DP入门题它逼你放弃枚举转而思考如何通过“状态”来复用信息。2. DP状态设计的核心思路2.1 从“以i结尾”这个状态定义切入很多DP题的状态设计是“前 i 个元素中满足条件的值”比如“前 i 个物品的最大价值”。但最大连续子序列有一个特殊性它要求结果必须是连续的如果只用“前 i 个元素的最大子序列和”作为状态你没法知道这个最大子序列的结尾在哪里也就没法判断能不能在后面继续延伸。换个角度想我们不需要知道全局最优子序列的所有细节只需要问一个问题——如果某个最优子序列恰好以第 i 个元素结尾它的最大和是多少于是就有了经典状态定义dp[i]表示以nums[i]结尾的连续子数组的最大和。这个定义的精妙之处在于它强制我们只关注“结尾固定在 i”的子数组。那么dp[i]只有两种可能的来源把nums[i]接到以nums[i-1]结尾的最优子数组后面也就是dp[i-1] nums[i]放弃前面所有元素让nums[i]单独成为一个新的子数组也就是nums[i]。两者取最大值就得到了转移方程dp[i] max(dp[i-1] nums[i], nums[i])初始条件dp[0] nums[0]因为以第一个元素结尾的子数组只有它自己。最终答案是所有dp[i]里的最大值因为全局最优子数组一定有一个确定的结尾下标。2.2 为什么这样定义最优你可能想问为什么“以 i 结尾”比“前 i 个元素”更合适我来对比一下两种思路的区别。如果定义f[i]为“前 i 个元素中最大连续子序列和”你想要从f[i-1]推导出f[i]遇到的核心难题是你不知道f[i-1]对应的子序列到底以哪个下标结尾也就无法确定当nums[i]加入时到底是“接上去”还是“新开一段”。你必须额外记录更多的信息比如那个子序列的左右端点维护起来非常麻烦。而dp[i]这个定义把状态压缩到“必须包含nums[i]”这个约束看起来让状态变“小”了实际上却让转移变得极其干净。全局答案虽然藏在了所有dp[i]的最大值里但每个中间状态自己就是“局部最优”信息没有丢失。这个“用强约束换清晰转移”的思路是DP设计里非常核心的心法。我再拿生活化类比帮没有接触过的人理解。想象你在一条流水线上每个工位都贴着一个标签“以我结尾的连续最优段”。第一个工位只能是自己。后面的工位面临两个选择要么接上前面那个工位的最优段继续干要么甩开前面自己重新成立一条流水线。哪个方案累计收益大就选哪个。最后全厂评比时各个工位的“最优段”放在一起比大小赢的那个就是全局最优。这个类比把状态设计、转移逻辑和最终答案的获取都说清楚了。2.3 Kadane算法DP的空间压缩版本上面定义的DP数组其实有一个明显的冗余计算dp[i]只用到了dp[i-1]最终答案也只需要在遍历过程中不断更新最大值。既然只依赖前一个状态我们完全不需要保留整个dp数组只需要两个变量cur当前以nums[i]结尾的最大和ans到目前为止的全局最大和。每遍历一个元素更新cur再用cur更新ans。这就是著名的 Kadane 算法时间复杂度 O(n)空间复杂度 O(1)。在很多面试场景下你写的最终解法就应该是这个版本而不是带数组的版本。3. 完整实操三种语言落地与正确性验证3.1 标准实现Python/Java/C对照我先把带DP数组的写法给出来因为它更直观适合讲解。Python版本def max_subarray_dp(nums): n len(nums) if n 0: return 0 dp [0] * n dp[0] nums[0] ans nums[0] for i in range(1, n): dp[i] max(dp[i - 1] nums[i], nums[i]) ans max(ans, dp[i]) return ans然后是Kadane空间压缩版def max_subarray_kadane(nums): cur ans nums[0] for x in nums[1:]: cur max(x, cur x) ans max(ans, cur) return ans这两段代码看着几乎一样但背后思路差异值得点破带dp数组的版本适合在面试讲解时画状态表帮助面试官跟上你的思路Kadane版则适合作为最终提交的代码变量少、不易写错、内存占用低。Java版本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; }C版本int maxSubArray(vectorint nums) { int cur nums[0]; int ans nums[0]; for (int i 1; i nums.size(); i) { cur max(nums[i], cur nums[i]); ans max(ans, cur); } return ans; }代码都极简真正要注意的反而是一些边界细节数组长度只有1时循环不会执行cur和ans都初始化为nums[0]结果正确。数组全为负数时cur每次都在“接上一个负数”和“自己单干”之间选择最终肯定选择所有负数中最大的那个结果也是正确的。这两种情况我建议你手动走一遍。3.2 手动推演一个完整用例拿[-2, 1, -3, 4, -1, 2, 1, -5, 4]走一遍Kadane的完整过程inums[i]curans0-2-2-211112-3-2134444-134525561667-5168456注意看 i2 这一步nums[2] -3cur更新为max(-3, 1 (-3)) -2。这里有意思的是cur变成了负数但后面nums[3] 4时cur更新为max(4, -2 4) 4因为4 2选择重新开始。这就是Kadane算法的关键行为一旦cur变为负数它对后续状态就没有正贡献了下一轮一定被“重新开始”的选项覆盖掉。最终答案是 6对应的子数组是[4, -1, 2, 1]。你可以手动加一下4-1216验算没问题。3.3 复杂度分析与面试时的表达要点时间复杂度是 O(n)因为只遍历数组一遍空间复杂度 O(1)因为只用了两个变量。面试时你需要主动说出这两句话并且解释一下为什么能达到这个复杂度——没有嵌套循环没有额外存储。这本身就比暴力解 O(n²) 有了质的提升。我建议你的表达顺序是先讲清楚暴力解为什么不可行再引出DP状态定义和转移方程最后说出Kadane压缩的动机。这个顺序能让面试官看到你不是背答案而是真的理解了解法的演进过程。实际操作中很多候选人一上来就甩最优解反而容易被追问到“为什么状态要这样定义”时卡壳。4. 高频变形与进阶场景4.1 要求输出最大子序列本身面试经常在原题基础上加一个需求不仅要输出最大和还要输出对应的子数组区间。这时候Kadane算法的两个变量就不够了需要额外记录最优解的起点和终点。核心技巧是当x cur x即选择重新开始时更新当前起点start i。当cur ans即更新全局最优时记录best_start start, best_end i。代码实现def max_subarray_with_indices(nums): cur ans nums[0] start end 0 cur_start 0 for i in range(1, len(nums)): if nums[i] cur nums[i]: cur nums[i] cur_start i else: cur cur nums[i] if cur ans: ans cur start cur_start end i return ans, start, end这个变形的坑在于必须在cur更新后再比较ans否则可能记录到旧状态的错误区间。我踩过一次坑就是先更新ans再更新cur结果在数组中途出现“局部最优被后续更优覆盖”时起点记录错误排查了很久才发现是更新顺序问题。4.2 环形数组最大子序和环形数组的意思是首尾相连子数组可以跨越原来的边界。LeetCode 918 就是这样一道题。解法思路很巧妙答案要么在数组内部要么跨越边界。内部情况就是普通Kadane跨越边界的情况等价于“整个数组的和减去内部最小子数组和”。最小子数组和可以用一个镜像的Kadane求把转移方程里的max改成min即可。最终答案取两者较大值。这里需要单独处理一个特殊情况如果所有元素都是负数普通Kadane求出的最大和就是最大的那个负数而“总和减最小子数组和”的答案会是 0因为最小子数组和等于总和此时应该直接返回内部那个负数最大值。这个边界不处理提交就会被隐藏用例卡住。4.3 分治法与线段树版虽然Kadane已经是 O(n)但分治法在另一个维度有价值它可以支持区间查询也就是动态修改数组后快速求任意区间的最大子段和。这种场景下你需要维护线段树每个节点存四个值sum区间总和lmax从左端点开始的最大前缀和rmax从右端点开始的最大后缀和tmax整个区间的最大连续子段和。合并两个子区间时tmax max(left.tmax, right.tmax, left.rmax right.lmax)。这个结构在动态维护股票收益、文本相似度峰值等问题中都有应用。虽然面试一般不要求写线段树但理解这个思路能让你在遇到“多次查询”类问题时多一个杀手锏。4.4 二维最大子矩阵把一维问题扩展到二维矩阵求一个子矩阵的最大和。常见解法是枚举矩阵的上下边界把上下边界之间的每一列压缩成一个数然后对压缩后的一维数组跑Kadane。这样时间复杂度是 O(n²·m)n 为行数m 为列数。这个技巧在图像处理里的最大连通区域亮度分析、推荐系统里用户行为矩阵的密集区间检测中都有应用场景。我自己在实现二维版本时最容易被坑的是“枚举上下边界”的双重循环顺序。建议外层固定上边界内层枚举下边界并同时维护每一列的累加值col_sum[j]这样每个内层循环都能在 O(m) 的时间跑一次Kadane总复杂度才可控。如果你每个上下边界都重新累加列值复杂度会退化到 O(n²·m²)那就失去了压缩的意义。5. 常见问题与排查技巧实录5.1 初始化边界条件最容易翻车cur和ans的初始化是我在给新人review代码时发现的最常见问题。有人喜欢把ans初始化为float(-inf)或者0这在数组全为负数时会直接出错。比如[-3, -1, -2]如果用0初始化ans最终答案会错误地输出 0而不是-1。正确写法永远是把cur和ans都初始化为nums[0]然后从下标 1 开始遍历。还有一种情况是输入数组可能为空。这时候应该返回什么面试时建议先和面试官确认通常返回 0 或抛出异常。但从严格意义上说空数组没有“最大连续子序列”返回 0 只是工程上的妥协需要你自己心里有数。5.2 另一个DP分支数位DP别混淆有些读者看到“DP”关键词可能会联想到“数位DP”。这里得明确一下本文讲的是用“动态规划”求解最大连续子序列和属于线性DP的基础分支而数位DP是解决“在某个范围内统计满足特定数位条件的数字个数”的一类问题例如统计 1 到 n 中不含某个数字的个数。两者虽然都叫DP但状态设计完全不同千万不要混为一谈。如果你感兴趣后续我可以单独写一篇数位DP的入门文章这里只提醒你搜索资料时注意区分。5.3 面试实战的避坑与表达技巧面试这道题时有几个表达上的小技巧我用了很多年效果一直不错。第一先画一个数组的例子。拿[-2, 1, -3, 4, -1, 2, 1, -5, 4]当白板例子一边讲一边手动更新cur和ans面试官能立刻跟上你的思路。空谈状态转移方程容易让人走神但一个活生生的例子能把抽象的DP讲得具体。第二主动说出“状态有后效性问题所以不能简单用前 i 个元素”。这句话是区分“背题”和“理解”的分水岭。面试官问出“为什么要以 i 结尾”时就是他想判断你到底懂不懂DP本质的时候。第三如果你被追问“能否用分治”不要慌。先把分治思路讲清楚最大子数组要么在左半、要么在右半、要么跨越中点然后补充跨越中点时需要从中间向两边扩展计算最大和时间复杂度 O(n log n)。如果你还能顺带提一句“分治适合处理需要区间合并的场景线段树是它的进阶版本”那基本就是一个接近满分的回答。5.4 工程实践中的真实场景我知道有些读者可能心里嘀咕这题刷了但实际工作里真的用得上吗答案是“用得上只是不那么显眼”。我在做音频波形峰值定位时遇到过需要在大量采样点中找到能量最集中的连续片段本质就是最大连续子序列和的变体只是把“和”换成了“能量积分”。做监控告警时判断一段时间内请求量持续上涨的区间也可以转化成类似问题。这些场景都有一个共同特点数据是顺序相关的且你需要找的是“连续且总量最大”的一段而不是离散的几个点。从这个角度看最大连续子序列不是一个孤立的面试题而是一整类“序列最佳区间”问题的基石。理解了它的状态设计思路很多看起来完全无关的问题——比如最大乘积子数组、最长湍流子数组——都能用同样的方法拆解。我个人在实际操作中的体会是这道题真正难的不是写出Kadane那几行代码而是在面对变形题时你能不能条件反射地想到“我应该强行定义一个包含当前位置的状态”。一旦你形成了这个思维习惯再遇到二维矩阵、环形数组、区间合并这些变体就都能顺藤摸瓜找到了路。把这个底层逻辑吃透比记住十道题的答案有用得多。