这道经典的“最大子数组和”题算是力扣hot100里被翻牌次数最多的题目之一了。很多人在面试的时候都会被问到但它绝不是背个动态转移方程就能糊弄过去的题。如果用一句话概括核心给你一个整数数组让你找到一个连续的子数组让它的和最大返回这个最大值。看起来简单但里面藏着动态规划、贪心、分治好几层值得琢磨的东西。这篇文章我会把这道题从暴力到最优解完整拆开把每一步“为什么这么做”讲清楚顺便把刷题时容易踩的坑和面试时可能的追问都列出来。不管你是刚接触算法的小白还是准备冲刺大厂面试的老手这篇都能帮你把这道题吃透。1. 题目到底在问什么1.1 用大白话理解题意先翻译成人话。给你一个数组比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]题目要你找一个连续的片段这个片段里的数字加起来的和是所有片段里最大的。注意“连续”这个词是重点。你不能跳着选打个比方这就好比在一列连续停靠的地铁站里选一段区间从A站坐到B站把每一站的客流量加起来找一个客流量总和最大的乘车区间。你不可能中间跳过某站也不能分段换乘只能是一路坐下去。再强调一下子数组要求元素在原数组中是连续相邻的。比如[4, -1, 2, 1]就是一个子数组它的和是6也是上面这个例子的答案。而[4, 2, 1]不是因为4和2在原数组中间隔着-1。1.2 暴力解法为什么不行很多人拿到题第一反应是我把所有子数组都枚举出来求个最大值不就行了吗思路没错但复杂度成问题。一个长度为n的数组子数组的数量是 $n*(n1)/2$ 个。如果对每个子数组再求和复杂度就是 $O(n^3)$。优化一点用前缀和可以把每个子数组求和优化到 $O(1)$这样总复杂度是 $O(n^2)$。但leetcode上数组长度动不动就是 $10^5$$O(n^2)$ 意味着要计算 $10^{10}$ 次必超时。所以要学会转变思路。暴力枚举之所以慢是因为它把“每个子数组”都当成独立个体重新计算。而更聪明的做法是找一个状态让后一个状态能从前一个状态转移过来这个状态就是“以某个位置结尾的最大子数组和”。1.3 这道题考察的能力最大子数组和是一道很典型的动态规划入门题但它考察的不只是动态规划。面试官可以从这道题延伸出很多考点状态定义是否清晰dp[i]表示什么很多人一开始会误以为dp[i]是整个数组的最大子数组和导致转移方程写不对。状态转移是否合理为什么取max(nums[i], dp[i-1] nums[i])这里面的逻辑能否讲清楚。空间优化如何从 O(n) 的dp数组降到 O(1)这体现你对状态依赖关系的敏感度。分治思想有些面试官会追问“如果不用贪心/DP你还能怎么做”此时分治解法就是加分项。边界处理数组全负数怎么办长度为1怎么办要不要允许空子数组这些细节决定了代码的健壮性。所以这道题看似简单其实是一座冰山水面下藏着很多面试官想捞的东西。2. 动态规划思路拆解从状态定义到状态转移2.1 状态定义dp[i]代表什么动态规划第一步是定义状态。我说一个很多人踩过的坑这道题最忌讳把dp[i]定义成“前i个元素中的最大子数组和”。为什么因为如果你这样定义当计算dp[i]时你需要知道“上一个最大子数组是否包含第i个元素”而这个信息你没存下来转移会很别扭。正确的状态定义是dp[i]表示以nums[i]作为结尾的连续子数组的最大和。注意“以 nums[i] 结尾”这几个字它是整道题的灵魂。把dp[i]理解为“数组的第 i 个位置必须被选中且这个子数组的终止位置必须在这里”。这样一来状态之间才有清晰的递推关系。举个例子数组[1, -2, 3]dp[0] 1以1结尾的最大和是1dp[1]以-2结尾的子数组有[-2]和[1, -2]最大和是-1dp[2]以3结尾的子数组有[3]、[-2, 3]、[1, -2, 3]最大和是3所以dp数组为[1, -1, 3]全局最大是3。2.2 状态转移方程的由来既然dp[i]是“以 i 结尾”的最大子数组和那么在上一个状态dp[i-1]的基础上考虑当我们要把nums[i]加入某个子数组时只有两种可能让nums[i]单独成为一个子数组也就是“从头开始”此时和为nums[i]。让nums[i]接在“以 i-1 结尾的最大子数组”后面此时和为dp[i-1] nums[i]。注意第2点为什么一定是dp[i-1]而不是别的前缀因为要以i结尾并且连续唯一能接的就是以i-1结尾的子数组。如果接的不是以i-1结尾的子数组中间就断开不连续了。所以转移方程就是dp[i] max(nums[i], dp[i-1] nums[i])等价写法是dp[i] nums[i] max(0, dp[i-1])后一种写法更好理解如果dp[i-1]是负数那我还不如不带它直接开一个新的子数组如果dp[i-1]是正数带上它能让和变大那就带。2.3 为什么答案不是dp[n-1]而是max(dp)这是很多新手最容易犯的错误。请你永远记住dp[i]只是“以 i 结尾”的最大和并不是整个数组的答案。真正的答案可能是以任意位置结尾的子数组中的最大值。比如数组[1, 2, -100, 3, 4]以最后一个位置4结尾的最大子数组是[3, 4]和是7刚好也是全局最大。但如果数组变成[5, -100, 1, 2]最后一个元素2结尾的最大和是3而全局最大其实是5。你不可能保证最大子数组一定结束在最后一个位置上。所以要么维护一个全局变量ans在计算每个dp[i]时更新它要么等dp数组算完后取max(dp)。2.4 空间压缩从O(n)到O(1)观察转移方程dp[i] max(nums[i], dp[i-1] nums[i])你会发现一个关键点计算当前状态只需要前一个状态不需要更早的状态。这是一个非常明显的“滚动更新”信号。于是我们完全没有必要开一个长度为 n 的dp数组只需要两个变量cur当前以 i 结尾的最大子数组和ans到目前为止的全局最大和循环里这样更新cur max(nums[i], cur nums[i]) ans max(ans, cur)这就是著名的Kadane算法也是这道题最优解的基本形态。它把空间复杂度从 O(n) 优化到了 O(1)。3. Kadane算法最优解的原理与代码实现3.1 Kadane算法的核心思想Kadane算法的名字听起来很高端其实本质就是“一边扫描一边更新当前连续和”。它采用的是贪心与动态规划结合的思想每到一个新位置我判断“之前积累的和”对我有没有帮助。如果帮助是正的我就继续累加如果帮助是负的还不如清零重来。这个“清零重来”的动作非常关键。生活化一点理解你手里攒了一堆钱但出现了负债。如果负债太多继续拿着只会越陷越深不如直接放弃旧账从今天重新开始攒。对应到算法中就是当cur nums[i]小于nums[i]时说明cur是负的负资产会拖累当前值所以选择从nums[i]作为新的起点。但要注意Kadane算法并不是真的切掉子数组它只是调整了“状态起点”。它的正确性建立在状态转移方程上cur永远代表以当前位置结尾的最大和这个值只会增加全局答案的可能不会丢解。3.2 代码实现C/Python/Java 示例给你几个主流语言的实现都是最优解直接抄作业没问题。先用Python写代码最简洁def maxSubArray(nums): cur ans nums[0] for num in nums[1:]: cur max(num, cur num) ans max(ans, cur) return ansC版本class Solution { public: 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; } };Java版本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; } }注意这里初始化的细节cur和ans都初始化为nums[0]而不是0。这一步很重要原因下面单独讲。3.3 边界条件与初始化细节先看数组全为负数的情况比如[-3, -4, -5]。如果初始化为0那么循环里cur max(-4, 0 (-4)) -4看起来没问题。但初值ans 0会导致最终返回0而题目要求子数组至少包含一个元素所以正确答案应该是-3。当nums[0]是负数时把它作为初始ans就能避免“空子数组”混进来。再看长度为1的数组比如[7]。直接用nums[0]初始化后不会进入循环返回7正确。还有一点需要和面试官确认题目是否允许返回空子数组的和0力扣原题不允许但有一些变体或者商业场景里空数组会被认为和为0。如果在面试中遇到这题建议先问清楚“这个子数组必须至少包含一个元素对吧”这会显得你考虑问题周全。3.4 时间复杂度与空间复杂度分析Kadane算法只遍历了一遍数组所以时间复杂度是 O(n)。空间上只用了常量个变量空间复杂度 O(1)。这里很容易在回答时展开为什么O(n)是最优的因为只靠输入数组你至少要把每个元素看一眼才有可能得出正确答案所以下界就是O(n)。分治法虽然也能做但复杂度是O(n log n)空间O(log n)并不如Kadane。所以Kadane是这道题在“答案只要求返回最大和”前提下的最优解。4. 分治解法另一种思考方式4.1 分治的核心逻辑如果面试官追问“除了动态规划还有什么方法”分治解法是个很好的加分答案。分治的思想是把数组从中间切一刀分成左半和右半。那么整个数组的最大子数组和只可能出现在三个地方完全在左半部分完全在右半部分跨越中点一半在左一半在右前两种情况直接递归解决就行问题规模变成原来的二分之一。第三种情况需要单独处理从中间位置分别向左和向右扩展找到左半部分以中点结尾的最大连续和以及右半部分以中点开头中点右侧第一个元素的最大连续和两者加起来就是跨过中点的最大子数组和。4.2 合并区间时的四种情况很多人分治写不出来卡就卡在“跨中点情况”的合并上。这里我给你拆成四个小步骤从mid开始向左累加记录过程中出现的最大值leftSum。从mid 1开始向右累加记录过程中出现的最大值rightSum。跨中点的最大和就是leftSum rightSum。最终答案取max(左递归结果, 右递归结果, 跨中点结果)。注意向左扩展时为什么不能停下来因为可能暂时的累加和是负数但再加上更左边的正数后总和又会变大所以必须一直扩展到左边界并动态记录峰值。同理向右扩展也要一直进行。4.3 分治代码实现这里我给你一个用Python写清楚的分治版本def maxSubArray(nums): def divide_and_conquer(l, r): if l r: return nums[l] mid (l r) // 2 # 左半部分递归 left_ans divide_and_conquer(l, mid) # 右半部分递归 right_ans divide_and_conquer(mid 1, r) # 跨中点向左扩展 left_sum 0 left_max float(-inf) for i in range(mid, l - 1, -1): left_sum nums[i] left_max max(left_max, left_sum) # 跨中点向右扩展 right_sum 0 right_max float(-inf) for i in range(mid 1, r 1): right_sum nums[i] right_max max(right_max, right_sum) cross_ans left_max right_max return max(left_ans, right_ans, cross_ans) return divide_and_conquer(0, len(nums) - 1)这个递归的终止条件是l r也就是只有一个元素时直接返回该元素。跨中点合并的复杂度是O(n)每一层都要对当前区间进行一次线性扫描。4.4 分治与动态规划的对比分治法的时间复杂度是 O(n log n)空间复杂度是递归栈的 O(log n)。虽然不如Kadane但它的思想在很多高级数据结构里会用到比如线段树维护区间最大子段和。如果你把分治扩展一下就能解决“多次区间查询最大子数组和”的动态问题这也是后面可以继续深入的方向。动态规划的优势是代码短、速度快、好理解分治的优势是结构清晰便于扩展。两个解法建议都掌握面试的时候可以主动展示你从不同角度理解同一个问题。5. 常见错误与调试技巧实录5.1 初始化踩坑dp[0]忘记赋值导致问题有的同学会写一版“看起来没问题”的代码cur 0 ans 0 for num in nums: cur max(num, cur num) ans max(ans, cur)这个写法在数组有正有负时能跑出正确答案因为最终答案不会是0。但一旦数组全部是负数比如[-1, -2, -3]这个代码会返回0而正确答案是 -1。原因就是ans初始化为0相当于默认允许了一个空子数组出现。力扣原题里这个答案就是错的。避免方法是把初始值设为nums[0]并且循环从1开始。5.2 返回最大值还是返回dp最后一个元素这个坑我在教学时见过很多次。你如果写的是dp [0] * n dp[0] nums[0] for i in range(1, n): dp[i] max(nums[i], dp[i-1] nums[i]) return dp[-1]那么当最大子数组不在数组末尾时就会返回错误结果。比如[5, -100, 1, 2]dp为[5, -95, 1, 3]dp[-1]3但正确答案是5。必须维护一个ans变量或者最后返回max(dp)。很多人面试时在这翻车别小看这个细节。5.3 负数组的测试用例刷题的时候习惯性多测几个边界用例是很好的习惯。我觉得这道题至少测这三组全正数组[1, 2, 3]期望输出 6全负数组[-1, -2, -3]期望输出 -1混合数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]期望输出 6尤其是全负数组最容易暴露初始化问题。很多看似正确的代码在普通用例能过到全负数组直接翻车。5.4 大数溢出的隐患如果数组元素是很大的整数比如10^9级别的数而且n也很大那么累加和可能超过int的表示范围。在C/Java里建议用long long或long来存cur和ans否则可能溢出得到错误结果。Python不用考虑这个因为整数可以无限大但在面试中如果你用C最好主动提一句“防止溢出用长整型”。6. 这类题型在面试中的延伸与应用6.1 变体一返回最大子数组的起止下标有时候光返回最大和还不够面试官会让你额外输出这个子数组在数组中的起始下标和结束下标。怎么改只需要在Kadane算法里多记录几个变量def maxSubArrayWithIndex(nums): cur ans nums[0] start end 0 tmp_start 0 for i in range(1, len(nums)): if cur nums[i] nums[i]: cur cur nums[i] else: cur nums[i] tmp_start i if cur ans: ans cur start tmp_start end i return ans, start, end这里的tmp_start是“当前子数组的临时起点”。当cur nums[i]小于nums[i]时说明我们决定从第i个元素重新开始所以临时起点更新为i。当cur刷新了ans时把临时起点和当前位置作为正式的起止下标。6.2 变体二环形数组最大子数组和如果数组是首尾相连的环形也就是你可以从末尾绕回开头找子数组那答案就有两种情况最大子数组没有跨越首尾边界它就是普通的最大子数组和。最大子数组跨越了首尾边界此时相当于从整个数组的和中减去一个“最小子数组和”。所以环形版本的解法是ans max(普通最大子数组和, total - 普通最小子数组和)但要注意如果数组全为负数普通最大子数组和就是最大的负数而total - 最小子数组和可能是0但空数组不允许所以这种情况要单独处理。这个变体在很多公司的面试题里出现过理解了这道题后环形版本其实就是在同一个思想上的小改造。6.3 变体三二维矩阵的最大子矩阵和还有一个进阶版本给定一个二维矩阵找一个子矩阵使得所有元素之和最大。这个问题的经典解法是一维最大子数组和的推广。具体做法是枚举矩阵的上边界和下边界把每一列的元素累加成一个一维数组然后对这个一维数组跑Kadane算法。这样一来二维问题就被压成了一维问题时间复杂度是O(n^3)。如果你把这道题吃透了“最大子矩阵”问题会轻松很多。6.4 贪心与动态规划的联系很多人分不清贪心和动态规划。在最大子数组和问题上Kadane算法其实同时具备贪心和动态规划两种视角。从状态转移角度看它是标准的动态规划从决策角度说每步只保留“以当前位置结尾的最大和”这是局部最优而局部最优又能推导出全局最优因此它也可以被理解为一种贪心策略。面试时如果能说出这句话“这题既可以用DP解释也可以用贪心解释Kadane算法是两者的结合”会给面试官留下很好的印象。说明你不只是在背代码而是理解了内在逻辑。最后再分享一个小技巧。刷这题时我建议你用手在纸上画两个例子一个是全负数一个是混合正负数。手动模拟一遍cur和ans的变化很多模糊的地方就会突然清晰起来。这道题代码虽然短但它几乎是所有“子数组类问题”的基石。把状态定义、转移方程、空间优化这三层吃透后面再遇到什么股票问题、最长递增子序列、最大子矩阵你都会有“原来都是同一个套路”的感觉。这道题我刷了很多遍每次给不同基础的人讲发现最后的瓶颈永远不是代码而是“为什么状态要定义成以i结尾”。别忘了这个核心比背十遍代码都有用。