最大子数组和与Kadane算法：从暴力到分治，搞定LeetCode 53-北京尧图网络

最近后台访问日志里有个自称“搜索机器人”的访客连续刷了好几条警告我一边清日志一边刷题正好复习到题库里的第 53 题 Maximum Subarray最大子数组和。这道题我前前后后用四种思路解过每次回头看都有新收获。这篇笔记适合刚学动态规划的读者也适合想在面试前把这道经典题彻底吃透的人。1. 这道题到底在问什么连续、非空、最大和1.1 题目本身的三个关键约束题目给一个整数数组比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]要求找到一个连续子数组让它的元素和最大最后返回这个最大和。以这个例子来说最优子数组是[4, -1, 2, 1]加起来是 6。很多人第一次读题会忽略三个细节。第一“连续”意味着不能排序、不能跳着选元素第二“子数组最少包含一个元素”所以不能返回空数组第三数组里可能全是负数比如[-1, -2, -3]此时最大子数组和是-1而不是 0。这三个约束基本决定了后面所有算法的设计方向。举个边界例子。输入[-3, -2, -1]遍历一遍就能发现以-1结尾的子数组和最大是-1因为单元素也算子数组。若有人把答案变量初始值设成 0这道题就会得出一个荒谬的结果 0。这类 bug 在真实面试中出现频率非常高后面我会专门讲。1.2 为什么这道题值得反复做在很多动态规划问题里状态设计往往要绕好几个弯但这一题的 dp 状态设计非常自然不需要复杂的分类讨论却又能完整体现“子问题、决策、状态转移、最优解”这条链路。再加上它可以用 O(n) 时间和 O(1) 额外空间完成是动态规划里少有的“短平快”题目。我见过 A 同学第一次写这题上来直接暴力三重循环答案对但时间复杂度 O(n^3)平台直接超时也见过某开发者用前缀和优化O(n^2) 勉强通过但完全没触及这类题的精髓。所以我建议每一位读者至少把这题做三遍第一遍暴力解理解题意第二遍动态规划理解转移方程第三遍分治法理解“区间信息合并”的概念。每一遍的收获完全不同。2. 从暴力枚举到状态转移核心方程的推导2.1 为什么暴力解能当引子如果面试官让你做这题最自然的第一反应是枚举所有可能的起点 i 和终点 j求区间和然后取最大值。直接三层循环是 O(n^3)如果用前缀和数组可以把区间求和从 O(n) 降到 O(1)整体复杂度变成 O(n^2)。下面这个代码用了“单层起点循环内层累加”本质上就是前缀和思路的简易版def max_subarray_brute(nums): n len(nums) ans float(-inf) for i in range(n): s 0 for j in range(i, n): s nums[j] if s ans: ans s return ans这个两层循环在n 10^5时要做大约 5 × 10^9 次累加任何普通判题系统都扛不住。暴力解真正的价值是帮我们验证题意的正确理解同时给后续的优化提供一个正确的对照基准。2.2 dp[i] 的定义为什么是“以 nums[i] 结尾”这是全题最关键的一步。定义dp[i]表示“以 nums[i] 作为最后一个元素的所有连续子数组里能取到的最大和”。注意这个定义没有限制子数组的开头在哪只要求它必须以 nums[i] 收尾。为什么这样定义因为连续子数组的拼接非常有规律如果已经知道了以nums[i-1]结尾的最大子数组和那么以nums[i]结尾的子数组只有两种来源把nums[i]接到前一个子数组后面得到dp[i-1] nums[i]只选nums[i]自己因为前一段累计结果已经是负数带上它只会拖累整体。所以转移方程是dp[i] max(dp[i-1] nums[i], nums[i])这个方程极其简洁但完整描述了一个关键判断当上一段“家底”已经是负的与其硬撑不如关门重新开张。2.3 一个可以让面试官点头的理解方式我经常用一个跟经营有关的比喻来解释这段逻辑。假设你经营的店铺每天盈亏可以用数组表示正数代表赚钱负数代表亏钱。你要找一段连续的日子让累计利润最高。如果截止昨天你手里的累计利润已经是负的今天又有一笔新的盈亏那你一定不应该带着昨天的亏损继续往里投钱干脆抹掉重置只从今天重新记账。反之如果昨天累计下来还是正收益今天当然继续加仓。这个比喻对应到代码就是两个选择要么在旧子数组后面“续上”要么“重新开始”。而“重新开始”只需要比较num和cur num谁更大然后取较大的那一个。想通了这一点Kadane 算法的代码就顺理成章了。2.4 空间压缩从数组到两个变量如果按 dp 数组来写代码会是dp [0] * n dp[0] nums[0] ans dp[0] for i in range(1, n): dp[i] max(dp[i-1] nums[i], nums[i]) ans max(ans, dp[i])因为dp[i]只依赖dp[i-1]我们根本不需要保留整个 dp 数组。用一个cur记录当前“以当前位置结尾的最大子数组和”再用一个ans记录历史全局最大值就足够了。这就是很多人听说的 Kadane 算法本质。3. 五行的 Kadane 实现与复杂度对照3.1 三种语言的极简实现Pythondef max_subarray(nums): cur ans nums[0] for i in range(1, len(nums)): num nums[i] cur max(num, cur num) ans max(ans, cur) return ansCint maxSubArray(vectorint nums) { int cur nums[0], ans nums[0]; for (int i 1; i nums.size(); i) { cur max(nums[i], cur nums[i]); ans max(ans, cur); } return ans; }JavaScriptvar maxSubArray function(nums) { let cur nums[0], ans nums[0]; for (let i 1; i nums.length; i) { cur Math.max(nums[i], cur nums[i]); ans Math.max(ans, cur); } return ans; };别看代码只有五行它把状态设计、转移决策、空间优化三件事全部浓缩完了。但真正面试时考官一定会追问一句“为什么要用max(num, cur num)”所以理解比默写更重要。3.2 复杂度对照表解法时间复杂度空间复杂度备注暴力枚举O(n^3)O(1)三层循环枚举 i、j、求和前缀和优化O(n^2)O(n)可优化到 O(1)但仍是平方级分治法O(n log n)O(log n)每层合并 O(n)递归栈 O(log n)动态规划/KadaneO(n)O(1)单次扫描最优解线段树式区间维护建立 O(n)查询 O(log n)O(n)支持动态修改与区间询问这个表在准备面试的时候特别有用。它说明 Kadane 在静态数组上是最优解之一但并不是所有场景都能用它——一旦题目要求“支持区间修改和区间查询最大子段和”线段树式维护就变成主要方案。这就是为什么我建议不要只背 Kadane分治法也要会。3.3 覆盖过的样例推演用[-2, 1, -3, 4, -1, 2, 1, -5, 4]走一遍。初始化cur -2, ans -2。遍历到 1max(1, -21) 1ans 变 1到 -3max(-3, 1-3) -2ans 保持 1到 4max(4, -24) 4ans 变 4到 -1max(-1, 4-1) 3到 2max(2, 32) 5到 1max(1, 51) 6到 -5max(-5, 6-5) 1到 4max(4, 14) 5。最终答案是 6。注意cur大多数时候是正数说明“家底”没有清零中间出现 -3 的那一步cur从 1 掉到 -2再到 4但ans始终保持住最大值 4 没有跟着下滑。这正印证了“历史最优”与“当前累计”分离的设计思路。4. 分治法拆开数组后每个区间要维护四样东西4.1 从递归角度重新看待这道题如果说 Kadane 是从左往右“顺势而为”的动态规划分治法就是经典的“先拆后合”。把数组从中间切成两半那么最大子数组和要么完全在左半段要么完全在右半段要么跨过中间线两边各取一部分。前面两种情况直接递归求解第三种情况需要从左半段靠右的部分取最大后缀和加上右半段靠左的部分取最大前缀和。于是每一层问题都被拆成了三个候选取最大值。这个思路看似比 Kadane 复杂时间复杂度 O(n log n)但它有一个巨大优势区间信息可以被“拼接”。为了支持任意两个相邻区间合并不能只保存区间最大子数组和这一项还需要额外保存 total区间总和、lmax区间内最大前缀和、rmax区间内最大后缀和、smax区间内最大子段和。4.2 合并公式假设左段信息是(lt, ll, lr, ls)右段信息是(rt, rl, rr, rs)合并成父节点total lt rtlmax max(ll, lt rl)rmax max(rr, rt lr)smax max(ls, rs, lr rl)这里有个容易绕晕的细节父节点的lmax有两种来源。要么是左段自己的最大前缀和此时前缀不跨过中线要么是左段整体加上右段最大前缀此时前缀从左段开头一直伸到右段某处。对应地父节点的rmax要么是右段自己的最大后缀和要么是右段整体加左段最大后缀。而smax除了左右各一半还要考虑跨线拼接即左段最大后缀加右段最大前缀。这一公式可以帮助理解“为什么不能只求三段中的最大值”。只求三段 max 的简化版本虽然也能得到正确答案但它无法处理“需要把整个区间作为前缀的一部分”的情况扩展性不够。4.3 用类线段树的方式写完struct Node { int total, lmax, rmax, smax; }; Node merge(Node a, Node b) { Node res; res.total a.total b.total; res.lmax max(a.lmax, a.total b.lmax); res.rmax max(b.rmax, b.total a.rmax); res.smax max(max(a.smax, b.smax), a.rmax b.lmax); return res; } Node solve(vectorint nums, int l, int r) { if (l r) return {nums[l], nums[l], nums[l], nums[l]}; int mid (l r) / 2; Node a solve(nums, l, mid); Node b solve(nums, mid 1, r); return merge(a, b); }将来遇到“带修改的区间最大子段和”问题时这套结构可以直接升级成线段树每个节点存储的正是这四个字段。这是我在准备这题时最大的一个收获通过一道简单题提前演练了更复杂数据结构的基础模块。4.4 分治法和 Kadane 的实际取舍单次询问的静态数组Kadane 完胜。分治常数更大递归还有栈开销。但如果问题变成“查询若干区间内各自的最大子段和”或者“修改某个位置后再查询”分治/线段树这套思路就显示出真正的价值。面试时如果你能主动提一句“这题还能用分治扩展成支持区间修改的线段树”通常能给面试官留下不错的印象。5. 进阶变体从一维到二维、环形与下标追踪5.1 不仅要最大和还要记录起止下标如果题目要求输出最大子数组的左端点和右端点Kadane 需要稍微改造当cur被重置为num即num cur num时新的起点就从当前位置开始。我在这个环节踩过坑先判断是否重置再判断是否更新答案结果在num cur num的相等边界上起止位置记录出现了偏差。稳妥做法是用一个临时变量记录候选起点在重置时更新它而在更新答案时才真正固定start和endcur ans nums[0] start end temp 0 for i in 1..n-1: if nums[i] cur nums[i]: cur nums[i] temp i else: cur cur nums[i] if cur ans: ans cur start temp end i这里重置条件用的是“大于”而不是“大于等于”。这样可以保证在相等情况下优先让子数组继续延伸保留更长的区间。我之前用时起点不断右移最终输出一个较短但和相等的子数组虽然数值对但题目要求顺序时就错了。5.2 环形数组变体如果数组首尾相接最大子数组只有两种可能要么是普通数组里的连续段要么是“跨过首尾绕了一圈”的段。第二种情况等价于“数组总和减去最小子数组和”。所以答案可以写成max(普通最大子段和, total - 最小子段和)。这里唯一的坑是子数组不能为空。如果数组全部是负数普通最大子段自然是最大的那个负数若走另一侧公式总和减去最小子段可能变成 0这是非法结果。解决办法是特判最大值是否小于 0如果小于 0 就直接返回该最大负数。5.3 二维矩阵的最大子矩阵矩阵版题目是在给定 m×n 矩阵中找一个子矩阵使元素和最大。常见做法是枚举子矩阵的上下边界 r1 和 r2把每一列在这两条边界之间的和压缩成一个一维数组然后对这个一维数组跑 Kadane。时间复杂度 O(m^2 × n)空间 O(n)。这个技巧在工程里也常常出现把二维问题通过列压缩降维成一维然后套核心算法。理解了第 53 题的一维 Kadane就等于理解了一整类“二维最大子矩阵”题目的核心组件。5.4 最大子段积的思路差异再看一个容易混的变体数组元素可能含负数要求连续子数组的最大乘积。此时贪心策略失效因为负负得正当前的“最小乘积”可能在未来变成最大。于是需要同时维护cur_max和cur_min转移时pre_max, pre_min cur_max, cur_min cur_max max(num, num * pre_max, num * pre_min) cur_min min(num, num * pre_max, num * pre_min) ans max(ans, cur_max)特别要注意这里不能直接写成cur_max max(num, num * cur_max, num * cur_min)因为后面的cur_min会被更新成新值两个变量互相依赖必须先用临时变量保存旧值。6. 面试现场与工程思维里那些容易翻车的细节6.1 面试官想听到的讲解顺序如果候选人只默写出五行代码面试官十有八九会追问“dp 状态为什么这么设计”。我建议的回答顺序是先说暴力 O(n^2) 和前缀和优化再引出dp[i]的定义和转移方程最后压缩空间讲成 Kadane。讲到“为什么用max(num, cur num)”时用经营重置的例子做辅助说明。能把这个链条讲清楚基本等同于把动态规划的第一课讲扎实了。6.2 三处高频 bugans 初始化问题如果ans 0遇到全负数数组会返回 0而不是正确结果。循环里漏掉nums[0]有些人从i 0开始跑还让cur初始化为 0结果第一个元素被忽略。更新时序问题先更新ans再更新cur通常没问题但别在计算cur时用已经被覆盖的上一轮值。其中第三点在做最大子段积的变体时特别明显两个变量互相依赖必须要用快照。这也是我反复强调“先在注释里写清变量语义再写代码”的原因。6.3 工程场景的联想处理股票收益序列、监控指标的最大连续上涨幅度、服务延迟序列的最长“不劣于阈值”区间这些问题本质都是“在线扫描维护最优历史”的模式。Kadane 并不是只在刷题时有用它的思想其实就是流式处理中经常说的“状态只保留必要历史其余全部丢掉”。日常实现中如果数据是持续到达的流O(1) 空间的做法往往比保存整个数组再离线计算更合适。比如实时监控系统里每个时间点只需要知道“当前延续的累计值”和“历史峰值”这两个变量就能回答“过去任意时刻的最大子段和是多少”这个问题。6.4 一个实践经验先写注释再写代码我后来的习惯是拿到这种题先把注释写清楚比如“cur 表示以当前位置结尾的最大子数组和”“ans 表示历史上所有位置的最大值”然后再补代码。这样做有个好处变量语义固定之后边界情况就很少出错。解题时思路飘忽的人大部分问题出在对变量没有精确的语义定义上。Kadane 看似简单但cur和ans各自语义一混乱输出就会千奇百怪。最后再分享一个我自己的小习惯。这题刷过几遍之后我把它和另外几个经典动态规划题放在同一个备忘录里爬楼梯、打家劫舍、买股票的最佳时机、最大子数组和。它们的状态定义各有特色但如果把状态转移方程并排放在一起看就能发现一个共同规律——所有 O(1) 空间的动态规划本质上都是在“只保留上一轮必要状态”的前提下通过一个小小的if/else或max/min来决定要不要“接续”或“重启”。第 53 题就是最典型的那个入口。如果你能把这道题的“为什么接续、为什么重启”给同事讲到对方点头那动态规划的基础就真的过关了。

最大子数组和与Kadane算法：从暴力到分治，搞定LeetCode 53

相关推荐

Linux内核启动早期内存映射：idmap与swapper_pg_dir深度解析

SAP HANA Merge机制与快捷登录：运维实战排查指南

SSE实时推送从原理到生产实践：比WebSocket更轻量

更多资讯

无人机视觉计数新方案：NGDINO显式数量建模实战

Python调海康相机SDK：环境配置到图像采集的实战指南

AI辅助A股复盘：四层指标体系与量价关系实战指南

YOLOv5自动脚本实战：从环境配置到避坑调优

银企直联对接工商银行：商业资料包如何减少联调返工

Spring Cloud Gateway整合Nacos：动态路由与灰度分流完整实践

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？