1. 先把问题嚼透什么是最大子数组和如果你刷过一段时间的算法题肯定绕不开这道“最大子数组和”。它几乎出现在每一份面试题单里也是动态规划入门时绕不开的经典案例。题目本身很简单给定一个整数数组找一个具有最大和的连续子数组返回这个最大和。注意关键词是“连续”这意味着你不能跳着选元素子数组必须是原数组中一段紧挨着的区间。举个例子数组是[-2, 1, -3, 4, -1, 2, 1, -5, 4]肉眼扫一下最大的连续子数组是[4, -1, 2, 1]和为6。这个结果很直观但真正困难的是当数组长度变成几万、几十万怎么用程序高效地找出来你总不能把所有连续子数组都列出来一个个求和吧这篇文章我想把三种经典解法从头到尾讲透暴力枚举法、分治法和动态规划法。这三种方法代表了三层递进的思考方式从“无脑遍历”到“分而治之”再到“用数学归纳法的思想做决策”。无论你是刚开始学算法的新手还是准备面试的求职者或者纯粹想复习基础知识的开发者都能从里面拿到一些可以立刻上手的东西。尤其是最后一种动态规划法它是面试中最爱考、效率也最高的解法值得你花时间彻底吃透。我自己的经验是这道题的价值不在“背答案”而在于它能把动态规划最重要的思想——状态定义、状态转移、空间优化——全部串起来。刷完这道题你对动态规划的感觉会完全不同。2. 暴力枚举法从最原始的思路出发2.1 三重循环直接枚举起点和终点刚接触这道题的人第一反应通常都是暴力枚举把所有的子数组都找出来分别求最大值。实现起来也非常简单使用两层循环分别控制子数组的起点i和终点j再写一层循环计算从i到j的和然后不断更新最大值。def max_subarray_brute_force(nums): n len(nums) max_sum float(-inf) for i in range(n): for j in range(i, n): current_sum 0 for k in range(i, j 1): current_sum nums[k] max_sum max(max_sum, current_sum) return max_sum这段代码的逻辑非常直白但问题也很致命三层循环嵌套时间复杂度是 O(n^3)。如果你拿一个一万个元素的数组去测运行时间会感人到让你怀疑人生。原因很简单——我们重复计算了大量区间和。比如你算完了nums[i:j]的和下个循环要算nums[i:j1]时又从头把nums[i]加到nums[j1]前面算过的结果完全没有利用上。这就是暴力法最大的问题不是错是傻。但在实际面试中先提出暴力法再逐步优化是一个非常标准的解题节奏。它至少帮你确认了一件事题目没有理解错枚举所有区间肯定是能得到正确答案的。这就相当于你到了一个陌生的城市先画一张粗糙的地图再慢慢细化精确路线。2.2 用前缀和消除最内层循环既然每次都重新求和太浪费那就想办法把“求和”变成“查表”。前缀和数组的经典做法是先预处理一个数组prefix其中prefix[i]表示nums[0]到nums[i-1]的和通常prefix[0] 0方便计算。这样求区间nums[i:j]的和只需要一步减法prefix[j1] - prefix[i]。def max_subarray_prefix(nums): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] max_sum float(-inf) for i in range(n): for j in range(i, n): current_sum prefix[j 1] - prefix[i] max_sum max(max_sum, current_sum) return max_sum这样时间复杂度从 O(n^3) 降到了 O(n^2)空间复杂度变成 O(n)用来存前缀和数组。别小看这一步优化它其实是“空间换时间”思想的典型体现。你牺牲了一点内存换掉了重复计算这在工程上很常见。还有一个细节值得注意前缀和数组多开一位让prefix[0] 0是为了让区间从0开始时也能用同一个公式表达。这个习惯我在处理大量区间求和问题时都会保持省得写一堆if i 0的特判。当然O(n^2) 的复杂度在面试里还是不够看的。如果数组长度是十万O(n^2) 意味着上百亿次操作现实场景完全顶不住。但从暴力到前缀和的这个过程你已经展现出了“发现问题并优化”的能力这在面试中是有加分的。前面两步只是热身接下来的两种方法才是真正的核心。2.3 暴力法的真正价值你可能会问既然后面有更优解法为什么还要花时间搞懂暴力法我个人的体会是暴力法是验证你对题目理解是否正确的试金石。尤其是当你实现完优化的算法后拿一个随机生成的小规模数组用暴力法的结果和优化算法的结果互相对拍这是最常见的自查手段。我平时写代码哪怕是处理一些业务逻辑也喜欢先用最容易读懂的方式写一个版本作为后续性能优化的参照物。这不是浪费时间而是帮你建立起“优化后结果依然正确”的信心。暴力法虽然效率低但它的正确性几乎不可能出问题这就是它最大的价值。3. 分治法把大问题切成两半想3.1 核心思想最大子数组只会出现在三个地方分治法的思路是和“连续”这个性质强相关的。我们把数组从中间分成左右两半那么要找的最大子数组只会出现在三个位置完全落在左半部分完全落在右半部分跨越了中间的分界线。前两种情况很好办递归去左半边和右半边分别求最大子数组和就行。麻烦的是第三种情况跨中点的最大子数组。这里的核心观察是如果一个子数组跨越了中点mid那么它必须包含nums[mid]和nums[mid1]。更准确地说它可以被拆成两部分从mid向左延伸的某个后缀加上从mid1向右延伸的某个前缀。于是跨中子数组的最大和就是“从mid向左的最大后缀和”加“从mid1向右的最大前缀和”。注意这里必须是连续的向左的部分必须终止于mid向右的部分必须起始于mid1。明白了这一点剩下的就是写清楚递归和合并逻辑。3.2 跨中点最大和的求解过程我们来写一个辅助函数cross_max(nums, left, mid, right)专门计算跨越中点的情况。它的做法是从mid开始向左累加记录过程中能得到的最大值再从mid1开始向右累加也同样记录最大值。两个最大值相加就是跨中点子数组的最大和。def cross_max(nums, left, mid, right): left_sum float(-inf) current_sum 0 for i in range(mid, left - 1, -1): current_sum nums[i] left_sum max(left_sum, current_sum) right_sum float(-inf) current_sum 0 for j in range(mid 1, right 1): current_sum nums[j] right_sum max(right_sum, current_sum) return left_sum right_sum为什么向左和向右要分开求最大值再相加而不是直接对整段求最大子数组因为我们要保证结果“跨过中点”。如果只在整个区间里用一次普通的最大子数组算法得到的可能是完全落在左边或者完全落在右边的结果那就不叫“跨中点”了。分开求的过程中向左的部分强制包含mid向右的部分强制包含mid1组合起来才满足跨越条件。这里有一个细节容易踩坑循环的边界条件。向左遍历时循环是从mid递减到left注意mid本身是包含在内的向右遍历时从mid 1递增到right。很多朋友在写的时候会把mid漏掉或者把right写成n导致结果出错。这种错误用前面提到的“和暴力法对拍”的方法一测就能暴露出来。3.3 递归主框架与复杂度分析写好了跨中点函数剩下的主逻辑就很清晰了。递归的终止条件是区间只剩一个元素此时最大子数组和就是这个元素本身。否则就拆成两半分别递归求解再结合跨中点结果取最大值。def max_subarray_divide(nums, left, right): if left right: return nums[left] mid (left right) // 2 left_max max_subarray_divide(nums, left, mid) right_max max_subarray_divide(nums, mid 1, right) cross_max_sum cross_max(nums, left, mid, right) return max(left_max, right_max, cross_max_sum)时间复杂度是 O(n log n)。怎么算出来的递归每一层需要线性扫描一遍数组主要是cross_max这一步左右加起来刚好是n个元素递归树的深度是 log n 层所以总复杂度是 O(n log n)。空间复杂度是 O(log n)来自递归栈的调用深度。分治法的优点在于它的思想很有普适性。很多看起来“没法下手”的问题只要你能找到“跨过中间合并”的方式就能用分治解决。它也是归并排序、快速排序这些经典排序算法的底层思想。虽然它的复杂度比不上动态规划但它在整个算法知识体系里的地位非常重要。我推荐新手阶段就把分治的套路练熟因为后面遇到树结构、区间查询、归并求逆序对等问题时你会发现它们的思想是一脉相承的。分治法的代码实现还有一个常见错误在递归函数里每次重新创建数组切片比如把nums[left:mid1]传给下一次递归。这样做不仅引入了额外空间开销还会让索引变得混乱。更好的做法是始终使用同一个数组只传递区间下标。这个习惯能让你减少很多不必要的 debug 时间。4. 动态规划法Kadane算法为什么是神4.1 状态定义为什么必须“以 i 结尾”动态规划法的核心是定义dp[i]表示“以nums[i]结尾的连续子数组的最大和”。第一次看到这个定义的人都会困惑为什么不直接定义成“前 i 个元素的最大子数组和”如果定义成后者转移的时候会遇到一个尴尬的问题你没法确定“前 i 个元素的最大子数组”到底是以第几个元素结尾的如果最后一个子数组的末尾不是nums[i-1]那它和nums[i]根本连不上。这就是“最优子结构”在这个题目里的关键陷阱。“以 i 结尾”的定义之所以精妙就在于它强制子数组延续到当前位置。那么当扫描到nums[i]时只有两种选择把nums[i]接在“以i-1结尾的最大子数组”后面形成一个新的连续子数组抛弃前面所有的累加值让nums[i]自己单独成为一个新的子数组。你可能会觉得第一种选择看起来总是更好毕竟前面累加了那么多。但别忘了如果前面的和是负数强行加上反而是累赘。比如数组是[-5, 2]如果非要接上-5结果变成-3还不如直接从2开始。所以状态转移方程就是dp[i] max(dp[i-1] nums[i], nums[i])。为什么这样定义后最终答案就是max(dp[0], dp[1], ..., dp[n-1])因为最大子数组的终点必然是数组中的某一个位置它的和就是对应的dp值。相当于我们枚举了所有可能的“子数组结尾位置”取其中的最大值。4.2 空间优化从一维数组到单个变量既然dp[i]只依赖dp[i-1]完全没有必要把所有中间结果存下来。用一个变量滚动更新即可这样空间复杂度从 O(n) 降到 O(1)。def max_subarray_kadane(nums): current_sum nums[0] max_sum nums[0] for i in range(1, len(nums)): current_sum max(current_sum nums[i], nums[i]) max_sum max(max_sum, current_sum) return max_sum这段代码简洁得让人怀疑这么复杂的问题就这几行但越简洁的代码越考验你对本质的把握。current_sum代表的其实就是“以当前元素结尾的最大子数组和”max_sum记录历史上出现过的最大值。每次循环我们只关心两件事接上当前元素是否划算以及当前结果是否刷新了历史最佳。这里还有一个容易犯的初始化错误把current_sum和max_sum初始化为0。如果数组中全是负数初始化成0就会导致最终答案错误。比如数组是[-3, -5, -1]最大子数组和应该是-1。但如果从0开始current_sum永远停留在0因为负数加上去会变小。所以正确的初始化方式是用数组的第一个元素这也是为什么上面代码里先赋值nums[0]再开始循环。这个坑在面试中非常常见十个人里至少有四个人会踩。4.3 Kadane算法背后的动态规划思想Kadane算法本质上就是动态规划只不过因为状态转移足够简单很多人没有意识到这一点。它的时间复杂度是 O(n)空间复杂度是 O(1)理论上已经是求解“最大子数组和”的最优解法。因为至少要遍历一次数组才能知道所有元素的情况所以 O(n) 就是下限。对于刚学动态规划的朋友我强烈建议你手动模拟一遍这个过程。拿[-2, 1, -3, 4, -1, 2, 1, -5, 4]来说i0current_sum -2max_sum -2i1max(-21, 1) 1max_sum 1i2max(1-3, -3) -2max_sum 1i3max(-24, 4) 4max_sum 4i4max(4-1, -1) 3max_sum 4i5max(32, 2) 5max_sum 5i6max(51, 1) 6max_sum 6i7max(6-5, -5) 1max_sum 6i8max(14, 4) 5max_sum 6最终答案是 6和题目给出的结果一致。这个过程走一遍你就能真正理解为什么要“贪心地抛弃负数前缀”因为扔掉负累赘永远是明智的选择。注意这里的“贪心”和普通的贪心算法不是一个概念它的依据是动态规划的递推关系并不是每一步只看局部最优。不过从效果上看它确实有一种“一旦发现累加值为负立刻从零开始”的直觉美感。5. 三足鼎立算法对比与实战选型5.1 复杂度与适用规模速查表三种算法放在一起对照各自的定位非常清晰。算法时间复杂度空间复杂度核心思想适用场景暴力枚举法O(n^3)O(1)枚举所有子数组小规模数据、验证正确性前缀和优化O(n^2)O(n)空间换时间中等规模、学习渐进优化分治法O(n log n)O(log n)分而治之、跨中点合并理解递归、树状分治思想动态规划法O(n)O(1)状态转移、滚动更新绝大多数工程与面试场景从表格中能明显看出动态规划法在各方面都是压倒性优势。这也是为什么面试时写代码直接用Kadane算法才是正确的答案。但分治法和暴力法也绝不是无用武之地在需要把问题扩展到二维矩阵、或者需要返回具体子数组区间时分治法和暴力法的思路有时会给你不一样的启发。5.2 面试和工程里怎么选如果是在面试现场我会建议你先口述暴力法的思路再快速过渡到动态规划。这个过程展示的是你的思维链——从最容易想到的方案出发识别其中的重复计算进而设计更优的状态定义。这种展示方式比直接甩出最优解法更有说服力因为面试官想看到的是你如何思考而不是你记忆力有多好。在真正的工程代码里最大子数组和问题很少会以裸题形式出现更多是作为某个复杂系统里一个内部步骤。比如处理传感器时序数据时找出信号最强烈的连续时间段或者在日志分析中找到某类错误持续爆发的连续区间。这些场景的数据量动辄几十万O(n^2) 根本跑不动所以直接上动态规划法是最稳妥的。但如果你还额外需要知道“最大和对应的子数组具体是从哪个下标到哪个下标”就得多写几行代码在更新max_sum时同步记录起点和终点。这里我再补一个工程细节当数组长度为0时Kadane算法会直接访问nums[0]从而抛出异常。所以真正落地时需要做空数组的判断并约定一个特殊返回值比如返回0还是抛出异常取决于业务语义。很多人刷题时不会遇到空数组的测试用例但在真实的业务代码里空数组的情况太常见了这一行防御性判断应该成为习惯。6. 延伸思考变体问题与实战经验6.1 四个值得研究的变体问题最大子数组和之所以经典是因为它有一大堆变体每一个都能考察你对基础版的理解深度。第一个变体是“返回最大子数组的起止下标”。解法是在Kadane算法进行中当current_sum被重置为nums[i]时记录新的起点为i当max_sum被刷新时记录当前的终点为i。这样最终就能找到对应的区间。第二个变体是“环形数组的最大子数组和”。环形数组意味着子数组可以绕过最后一个元素回到开头。比如[5, -3, 5]普通线性扫描得到最大子数组和是7[5, -3, 5]但环形情况下其实整个数组都是正收益最大和是7但如果数组是[5, -3, 5, 5, -3]情况就变得更复杂。经典做法是分两种情况讨论最大子数组不跨越边界直接用普通Kadane最大子数组跨越边界等价于“数组总和减去最小子数组和”。取两种情况的最大值即可。不过有个特殊情况如果数组全是负数总和减去最小子数组和会得到一个负数此时取普通Kadane的结果更合理需要额外判断。第三个变体是“二维矩阵的最大子矩阵和”。做法是把矩阵的若干行压缩成一个一维数组再对这个数组套用Kadane算法。具体来说枚举矩形的上下边界把每一列对应区间的元素累加成一个一维数组然后用一维最大子数组和找横向最大值。枚举上下边界是 O(n^2)每轮跑一次Kadane是 O(m)总复杂度是 O(n^2 * m)。这个方法在实际面试中遇到的可能性不大但能掌握的话会让你对动态规划的理解更上一层。第四个变体是“最大子序列和”也就是允许任意跳选的子序列而不是连续子数组。这个问题反而简单把所有正数累加就是答案如果全是负数就取最大的负数。虽然解法简单但它提醒我们一个重要的区分连续和离散的约束直接改变了问题的难度层级。6.2 刷这道题时我总结的几个自查方法我做算法题有个习惯就是写完代码后先不急着提交而是用几个特别设计的例子做自查。对最大子数组和来说我一定会测以下几类数据第一个是全负数数组比如[-3, -2, -1]。这个用例专门检测初始化值有没有写错如果返回了0说明初始化逻辑有 bug。第二个是只有一个元素的数组比如[7]。这个用例检测边界条件很多递归实现会在区间长度为1时出错。第三个是正负交替的数组比如[1, -2, 3, -1, 2]用来确认算法能正确处理“抛弃负数前缀再重新累加”的场景。第四个就是全正数数组比如[1, 2, 3, 4]此时答案应该是所有元素之和用来检测是否漏掉了某个位置的更新。还有一个调试技巧当代码结果不对时在Kadane算法的循环里打印i、current_sum、max_sum三个变量跟着输出走一遍往往几秒钟就能定位到问题。比盯着一堆代码空想要高效得多。分治法的递归实现如果出错建议在递归函数入口打印当前的left和right看看递归拆分是否符合预期同时把cross_max的结果单独验证因为这一块是最容易写错边界的地方。我在实际工作中还发现一个有意思的场景做数据监控时假设某个指标每天有一个波动值想找出一段“连续增长最猛”的时间窗口本质上就是在求最大子数组和。把每天的波动值放进数组跑一遍Kadane算法就能知道哪段时间整体表现最强。这种从算法题到工程应用的迁移感是刷题最让人上瘾的地方。最后再说说这道题留给我的一个深刻印象动态规划的状态定义一定要贴合“转移的需要”。有时候你定义的dp[i]看起来差不太多但“差之毫厘谬以千里”。在做其他动态规划题目时比如最长递增子序列、背包问题我都会先停下来认真想清楚——当前状态到底应该“以 i 结尾”还是“前 i 个元素”这个选择直接决定整个算法的成败。最大子数组和这道题教会我的正是这种状态定义的敏感性。
1. 先把问题嚼透什么是最大子数组和如果你刷过一段时间的算法题肯定绕不开这道“最大子数组和”。它几乎出现在每一份面试题单里也是动态规划入门时绕不开的经典案例。题目本身很简单给定一个整数数组找一个具有最大和的连续子数组返回这个最大和。注意关键词是“连续”这意味着你不能跳着选元素子数组必须是原数组中一段紧挨着的区间。举个例子数组是[-2, 1, -3, 4, -1, 2, 1, -5, 4]肉眼扫一下最大的连续子数组是[4, -1, 2, 1]和为6。这个结果很直观但真正困难的是当数组长度变成几万、几十万怎么用程序高效地找出来你总不能把所有连续子数组都列出来一个个求和吧这篇文章我想把三种经典解法从头到尾讲透暴力枚举法、分治法和动态规划法。这三种方法代表了三层递进的思考方式从“无脑遍历”到“分而治之”再到“用数学归纳法的思想做决策”。无论你是刚开始学算法的新手还是准备面试的求职者或者纯粹想复习基础知识的开发者都能从里面拿到一些可以立刻上手的东西。尤其是最后一种动态规划法它是面试中最爱考、效率也最高的解法值得你花时间彻底吃透。我自己的经验是这道题的价值不在“背答案”而在于它能把动态规划最重要的思想——状态定义、状态转移、空间优化——全部串起来。刷完这道题你对动态规划的感觉会完全不同。2. 暴力枚举法从最原始的思路出发2.1 三重循环直接枚举起点和终点刚接触这道题的人第一反应通常都是暴力枚举把所有的子数组都找出来分别求最大值。实现起来也非常简单使用两层循环分别控制子数组的起点i和终点j再写一层循环计算从i到j的和然后不断更新最大值。def max_subarray_brute_force(nums): n len(nums) max_sum float(-inf) for i in range(n): for j in range(i, n): current_sum 0 for k in range(i, j 1): current_sum nums[k] max_sum max(max_sum, current_sum) return max_sum这段代码的逻辑非常直白但问题也很致命三层循环嵌套时间复杂度是 O(n^3)。如果你拿一个一万个元素的数组去测运行时间会感人到让你怀疑人生。原因很简单——我们重复计算了大量区间和。比如你算完了nums[i:j]的和下个循环要算nums[i:j1]时又从头把nums[i]加到nums[j1]前面算过的结果完全没有利用上。这就是暴力法最大的问题不是错是傻。但在实际面试中先提出暴力法再逐步优化是一个非常标准的解题节奏。它至少帮你确认了一件事题目没有理解错枚举所有区间肯定是能得到正确答案的。这就相当于你到了一个陌生的城市先画一张粗糙的地图再慢慢细化精确路线。2.2 用前缀和消除最内层循环既然每次都重新求和太浪费那就想办法把“求和”变成“查表”。前缀和数组的经典做法是先预处理一个数组prefix其中prefix[i]表示nums[0]到nums[i-1]的和通常prefix[0] 0方便计算。这样求区间nums[i:j]的和只需要一步减法prefix[j1] - prefix[i]。def max_subarray_prefix(nums): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] max_sum float(-inf) for i in range(n): for j in range(i, n): current_sum prefix[j 1] - prefix[i] max_sum max(max_sum, current_sum) return max_sum这样时间复杂度从 O(n^3) 降到了 O(n^2)空间复杂度变成 O(n)用来存前缀和数组。别小看这一步优化它其实是“空间换时间”思想的典型体现。你牺牲了一点内存换掉了重复计算这在工程上很常见。还有一个细节值得注意前缀和数组多开一位让prefix[0] 0是为了让区间从0开始时也能用同一个公式表达。这个习惯我在处理大量区间求和问题时都会保持省得写一堆if i 0的特判。当然O(n^2) 的复杂度在面试里还是不够看的。如果数组长度是十万O(n^2) 意味着上百亿次操作现实场景完全顶不住。但从暴力到前缀和的这个过程你已经展现出了“发现问题并优化”的能力这在面试中是有加分的。前面两步只是热身接下来的两种方法才是真正的核心。2.3 暴力法的真正价值你可能会问既然后面有更优解法为什么还要花时间搞懂暴力法我个人的体会是暴力法是验证你对题目理解是否正确的试金石。尤其是当你实现完优化的算法后拿一个随机生成的小规模数组用暴力法的结果和优化算法的结果互相对拍这是最常见的自查手段。我平时写代码哪怕是处理一些业务逻辑也喜欢先用最容易读懂的方式写一个版本作为后续性能优化的参照物。这不是浪费时间而是帮你建立起“优化后结果依然正确”的信心。暴力法虽然效率低但它的正确性几乎不可能出问题这就是它最大的价值。3. 分治法把大问题切成两半想3.1 核心思想最大子数组只会出现在三个地方分治法的思路是和“连续”这个性质强相关的。我们把数组从中间分成左右两半那么要找的最大子数组只会出现在三个位置完全落在左半部分完全落在右半部分跨越了中间的分界线。前两种情况很好办递归去左半边和右半边分别求最大子数组和就行。麻烦的是第三种情况跨中点的最大子数组。这里的核心观察是如果一个子数组跨越了中点mid那么它必须包含nums[mid]和nums[mid1]。更准确地说它可以被拆成两部分从mid向左延伸的某个后缀加上从mid1向右延伸的某个前缀。于是跨中子数组的最大和就是“从mid向左的最大后缀和”加“从mid1向右的最大前缀和”。注意这里必须是连续的向左的部分必须终止于mid向右的部分必须起始于mid1。明白了这一点剩下的就是写清楚递归和合并逻辑。3.2 跨中点最大和的求解过程我们来写一个辅助函数cross_max(nums, left, mid, right)专门计算跨越中点的情况。它的做法是从mid开始向左累加记录过程中能得到的最大值再从mid1开始向右累加也同样记录最大值。两个最大值相加就是跨中点子数组的最大和。def cross_max(nums, left, mid, right): left_sum float(-inf) current_sum 0 for i in range(mid, left - 1, -1): current_sum nums[i] left_sum max(left_sum, current_sum) right_sum float(-inf) current_sum 0 for j in range(mid 1, right 1): current_sum nums[j] right_sum max(right_sum, current_sum) return left_sum right_sum为什么向左和向右要分开求最大值再相加而不是直接对整段求最大子数组因为我们要保证结果“跨过中点”。如果只在整个区间里用一次普通的最大子数组算法得到的可能是完全落在左边或者完全落在右边的结果那就不叫“跨中点”了。分开求的过程中向左的部分强制包含mid向右的部分强制包含mid1组合起来才满足跨越条件。这里有一个细节容易踩坑循环的边界条件。向左遍历时循环是从mid递减到left注意mid本身是包含在内的向右遍历时从mid 1递增到right。很多朋友在写的时候会把mid漏掉或者把right写成n导致结果出错。这种错误用前面提到的“和暴力法对拍”的方法一测就能暴露出来。3.3 递归主框架与复杂度分析写好了跨中点函数剩下的主逻辑就很清晰了。递归的终止条件是区间只剩一个元素此时最大子数组和就是这个元素本身。否则就拆成两半分别递归求解再结合跨中点结果取最大值。def max_subarray_divide(nums, left, right): if left right: return nums[left] mid (left right) // 2 left_max max_subarray_divide(nums, left, mid) right_max max_subarray_divide(nums, mid 1, right) cross_max_sum cross_max(nums, left, mid, right) return max(left_max, right_max, cross_max_sum)时间复杂度是 O(n log n)。怎么算出来的递归每一层需要线性扫描一遍数组主要是cross_max这一步左右加起来刚好是n个元素递归树的深度是 log n 层所以总复杂度是 O(n log n)。空间复杂度是 O(log n)来自递归栈的调用深度。分治法的优点在于它的思想很有普适性。很多看起来“没法下手”的问题只要你能找到“跨过中间合并”的方式就能用分治解决。它也是归并排序、快速排序这些经典排序算法的底层思想。虽然它的复杂度比不上动态规划但它在整个算法知识体系里的地位非常重要。我推荐新手阶段就把分治的套路练熟因为后面遇到树结构、区间查询、归并求逆序对等问题时你会发现它们的思想是一脉相承的。分治法的代码实现还有一个常见错误在递归函数里每次重新创建数组切片比如把nums[left:mid1]传给下一次递归。这样做不仅引入了额外空间开销还会让索引变得混乱。更好的做法是始终使用同一个数组只传递区间下标。这个习惯能让你减少很多不必要的 debug 时间。4. 动态规划法Kadane算法为什么是神4.1 状态定义为什么必须“以 i 结尾”动态规划法的核心是定义dp[i]表示“以nums[i]结尾的连续子数组的最大和”。第一次看到这个定义的人都会困惑为什么不直接定义成“前 i 个元素的最大子数组和”如果定义成后者转移的时候会遇到一个尴尬的问题你没法确定“前 i 个元素的最大子数组”到底是以第几个元素结尾的如果最后一个子数组的末尾不是nums[i-1]那它和nums[i]根本连不上。这就是“最优子结构”在这个题目里的关键陷阱。“以 i 结尾”的定义之所以精妙就在于它强制子数组延续到当前位置。那么当扫描到nums[i]时只有两种选择把nums[i]接在“以i-1结尾的最大子数组”后面形成一个新的连续子数组抛弃前面所有的累加值让nums[i]自己单独成为一个新的子数组。你可能会觉得第一种选择看起来总是更好毕竟前面累加了那么多。但别忘了如果前面的和是负数强行加上反而是累赘。比如数组是[-5, 2]如果非要接上-5结果变成-3还不如直接从2开始。所以状态转移方程就是dp[i] max(dp[i-1] nums[i], nums[i])。为什么这样定义后最终答案就是max(dp[0], dp[1], ..., dp[n-1])因为最大子数组的终点必然是数组中的某一个位置它的和就是对应的dp值。相当于我们枚举了所有可能的“子数组结尾位置”取其中的最大值。4.2 空间优化从一维数组到单个变量既然dp[i]只依赖dp[i-1]完全没有必要把所有中间结果存下来。用一个变量滚动更新即可这样空间复杂度从 O(n) 降到 O(1)。def max_subarray_kadane(nums): current_sum nums[0] max_sum nums[0] for i in range(1, len(nums)): current_sum max(current_sum nums[i], nums[i]) max_sum max(max_sum, current_sum) return max_sum这段代码简洁得让人怀疑这么复杂的问题就这几行但越简洁的代码越考验你对本质的把握。current_sum代表的其实就是“以当前元素结尾的最大子数组和”max_sum记录历史上出现过的最大值。每次循环我们只关心两件事接上当前元素是否划算以及当前结果是否刷新了历史最佳。这里还有一个容易犯的初始化错误把current_sum和max_sum初始化为0。如果数组中全是负数初始化成0就会导致最终答案错误。比如数组是[-3, -5, -1]最大子数组和应该是-1。但如果从0开始current_sum永远停留在0因为负数加上去会变小。所以正确的初始化方式是用数组的第一个元素这也是为什么上面代码里先赋值nums[0]再开始循环。这个坑在面试中非常常见十个人里至少有四个人会踩。4.3 Kadane算法背后的动态规划思想Kadane算法本质上就是动态规划只不过因为状态转移足够简单很多人没有意识到这一点。它的时间复杂度是 O(n)空间复杂度是 O(1)理论上已经是求解“最大子数组和”的最优解法。因为至少要遍历一次数组才能知道所有元素的情况所以 O(n) 就是下限。对于刚学动态规划的朋友我强烈建议你手动模拟一遍这个过程。拿[-2, 1, -3, 4, -1, 2, 1, -5, 4]来说i0current_sum -2max_sum -2i1max(-21, 1) 1max_sum 1i2max(1-3, -3) -2max_sum 1i3max(-24, 4) 4max_sum 4i4max(4-1, -1) 3max_sum 4i5max(32, 2) 5max_sum 5i6max(51, 1) 6max_sum 6i7max(6-5, -5) 1max_sum 6i8max(14, 4) 5max_sum 6最终答案是 6和题目给出的结果一致。这个过程走一遍你就能真正理解为什么要“贪心地抛弃负数前缀”因为扔掉负累赘永远是明智的选择。注意这里的“贪心”和普通的贪心算法不是一个概念它的依据是动态规划的递推关系并不是每一步只看局部最优。不过从效果上看它确实有一种“一旦发现累加值为负立刻从零开始”的直觉美感。5. 三足鼎立算法对比与实战选型5.1 复杂度与适用规模速查表三种算法放在一起对照各自的定位非常清晰。算法时间复杂度空间复杂度核心思想适用场景暴力枚举法O(n^3)O(1)枚举所有子数组小规模数据、验证正确性前缀和优化O(n^2)O(n)空间换时间中等规模、学习渐进优化分治法O(n log n)O(log n)分而治之、跨中点合并理解递归、树状分治思想动态规划法O(n)O(1)状态转移、滚动更新绝大多数工程与面试场景从表格中能明显看出动态规划法在各方面都是压倒性优势。这也是为什么面试时写代码直接用Kadane算法才是正确的答案。但分治法和暴力法也绝不是无用武之地在需要把问题扩展到二维矩阵、或者需要返回具体子数组区间时分治法和暴力法的思路有时会给你不一样的启发。5.2 面试和工程里怎么选如果是在面试现场我会建议你先口述暴力法的思路再快速过渡到动态规划。这个过程展示的是你的思维链——从最容易想到的方案出发识别其中的重复计算进而设计更优的状态定义。这种展示方式比直接甩出最优解法更有说服力因为面试官想看到的是你如何思考而不是你记忆力有多好。在真正的工程代码里最大子数组和问题很少会以裸题形式出现更多是作为某个复杂系统里一个内部步骤。比如处理传感器时序数据时找出信号最强烈的连续时间段或者在日志分析中找到某类错误持续爆发的连续区间。这些场景的数据量动辄几十万O(n^2) 根本跑不动所以直接上动态规划法是最稳妥的。但如果你还额外需要知道“最大和对应的子数组具体是从哪个下标到哪个下标”就得多写几行代码在更新max_sum时同步记录起点和终点。这里我再补一个工程细节当数组长度为0时Kadane算法会直接访问nums[0]从而抛出异常。所以真正落地时需要做空数组的判断并约定一个特殊返回值比如返回0还是抛出异常取决于业务语义。很多人刷题时不会遇到空数组的测试用例但在真实的业务代码里空数组的情况太常见了这一行防御性判断应该成为习惯。6. 延伸思考变体问题与实战经验6.1 四个值得研究的变体问题最大子数组和之所以经典是因为它有一大堆变体每一个都能考察你对基础版的理解深度。第一个变体是“返回最大子数组的起止下标”。解法是在Kadane算法进行中当current_sum被重置为nums[i]时记录新的起点为i当max_sum被刷新时记录当前的终点为i。这样最终就能找到对应的区间。第二个变体是“环形数组的最大子数组和”。环形数组意味着子数组可以绕过最后一个元素回到开头。比如[5, -3, 5]普通线性扫描得到最大子数组和是7[5, -3, 5]但环形情况下其实整个数组都是正收益最大和是7但如果数组是[5, -3, 5, 5, -3]情况就变得更复杂。经典做法是分两种情况讨论最大子数组不跨越边界直接用普通Kadane最大子数组跨越边界等价于“数组总和减去最小子数组和”。取两种情况的最大值即可。不过有个特殊情况如果数组全是负数总和减去最小子数组和会得到一个负数此时取普通Kadane的结果更合理需要额外判断。第三个变体是“二维矩阵的最大子矩阵和”。做法是把矩阵的若干行压缩成一个一维数组再对这个数组套用Kadane算法。具体来说枚举矩形的上下边界把每一列对应区间的元素累加成一个一维数组然后用一维最大子数组和找横向最大值。枚举上下边界是 O(n^2)每轮跑一次Kadane是 O(m)总复杂度是 O(n^2 * m)。这个方法在实际面试中遇到的可能性不大但能掌握的话会让你对动态规划的理解更上一层。第四个变体是“最大子序列和”也就是允许任意跳选的子序列而不是连续子数组。这个问题反而简单把所有正数累加就是答案如果全是负数就取最大的负数。虽然解法简单但它提醒我们一个重要的区分连续和离散的约束直接改变了问题的难度层级。6.2 刷这道题时我总结的几个自查方法我做算法题有个习惯就是写完代码后先不急着提交而是用几个特别设计的例子做自查。对最大子数组和来说我一定会测以下几类数据第一个是全负数数组比如[-3, -2, -1]。这个用例专门检测初始化值有没有写错如果返回了0说明初始化逻辑有 bug。第二个是只有一个元素的数组比如[7]。这个用例检测边界条件很多递归实现会在区间长度为1时出错。第三个是正负交替的数组比如[1, -2, 3, -1, 2]用来确认算法能正确处理“抛弃负数前缀再重新累加”的场景。第四个就是全正数数组比如[1, 2, 3, 4]此时答案应该是所有元素之和用来检测是否漏掉了某个位置的更新。还有一个调试技巧当代码结果不对时在Kadane算法的循环里打印i、current_sum、max_sum三个变量跟着输出走一遍往往几秒钟就能定位到问题。比盯着一堆代码空想要高效得多。分治法的递归实现如果出错建议在递归函数入口打印当前的left和right看看递归拆分是否符合预期同时把cross_max的结果单独验证因为这一块是最容易写错边界的地方。我在实际工作中还发现一个有意思的场景做数据监控时假设某个指标每天有一个波动值想找出一段“连续增长最猛”的时间窗口本质上就是在求最大子数组和。把每天的波动值放进数组跑一遍Kadane算法就能知道哪段时间整体表现最强。这种从算法题到工程应用的迁移感是刷题最让人上瘾的地方。最后再说说这道题留给我的一个深刻印象动态规划的状态定义一定要贴合“转移的需要”。有时候你定义的dp[i]看起来差不太多但“差之毫厘谬以千里”。在做其他动态规划题目时比如最长递增子序列、背包问题我都会先停下来认真想清楚——当前状态到底应该“以 i 结尾”还是“前 i 个元素”这个选择直接决定整个算法的成败。最大子数组和这道题教会我的正是这种状态定义的敏感性。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
