这题可以说是动态规划里最经典的入门例子了也是各大厂笔试和面试里出现频率极高的一道题。很多人第一次接触“最大子数组和”的时候第一反应是暴力枚举所有子数组然后求最大值但数据量一上来就超时了。用动态规划去拆解它不仅能把时间复杂度压到O(n)而且整个思考过程能帮你建立一套处理“连续子序列”问题的通用方法论。这篇文章就从问题本身开始一步步拆解动态规划的思路、C实现细节、边界坑点再到几个高频变体把这道题吃透。1. 问题理解先搞清楚题目在问什么1.1 题目描述与示例最大子数组和的标准描述是给定一个整数数组 nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。光看定义可能有点抽象直接看例子。假设数组是 [-2, 1, -3, 4, -1, 2, 1, -5, 4]那么连续子数组 [4, -1, 2, 1] 的和最大等于 6。注意子数组必须是连续的也就是在原数组中挨在一起的元素才能组成子数组不能跳着选。这和“子序列”不同子序列允许跳过中间的元素。还有一个关键点子数组最少包含一个元素。也就是说你不能选一个空数组然后说它的和是 0这个约束直接影响边界情况的处理后面我会专门讲。1.2 暴力解法先看最朴素的做法在动笔写动态规划之前我建议所有新手先尝试写一版暴力解法不是为了用而是为了感受问题的规模。最暴力的做法是三重循环外层起点 i内层终点 j再内层求 sum(nums[i..j])。这样时间复杂度是O(n^3)。优化一下用前缀和或者滑动累加的方式可以做到 O(n^2)也就是固定起点 i然后终点 j 依次往后走边走边累加记录过程中出现的最大和。代码大概长这样int maxSubArrayBruteForce(vectorint nums) { int n nums.size(); int ans INT_MIN; for (int i 0; i n; i) { int sum 0; for (int j i; j n; j) { sum nums[j]; ans max(ans, sum); } } return ans; }O(n^2) 在数组长度几千的时候勉强能跑但一旦数组规模到 10^5 甚至 10^6这个复杂度就完全不可接受了。10^5 的平方是 10^10 次操作在普通机器上要跑几十秒甚至几分钟这显然不行。这就是我们引入动态规划的动机把重复计算干掉把问题拆成可以递推的子问题。2. 动态规划思路从“以谁结尾”开始想2.1 子问题拆分动态规划的核心是先定义好状态。对于最大子数组和一个很多人初学时困惑的点是状态到底该怎么定义为什么不能定义成“前 i 个元素的最大子数组和”我们试一下这个定义dp[i] 表示前 i 个元素中最大子数组和。这个定义看着挺自然但它有个问题。假设我要求 dp[i] 的值我确实可以用 dp[i-1] 和包含 nums[i] 的情况比较但“包含 nums[i] 的情况”不一定得到的是 dp[i-1] 加 nums[i]。因为 dp[i-1] 对应的最优子数组可能并不以第 i-1 个元素结尾也就是说这个子数组和 nums[i] 之间可能有间隔拼起来就不连续了。所以状态定义必须体现“连续性”这个核心约束。正确的定义是dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。换句话说dp[i] 描述的“最优解”一定是包含了 nums[i] 这个元素并且是以它结尾的。这样定义的好处是如果要扩展到 dp[i1]由于连续性的要求dp[i] 对应的子数组不管内部长什么样它是以 nums[i] 结尾的所以它的末尾天然紧挨着 nums[i1]可以直接拼接。2.2 状态转移方程推导有了状态定义接下来就是找它们之间的递推关系。对 dp[i] 来说以 nums[i] 结尾的子数组本质上只有两种构成方式只有 nums[i] 自己一个人前面什么都不要。以 nums[i-1] 结尾的最大子数组再加上 nums[i]。为什么只有这两种因为连续子数组必须以 nums[i] 结尾所以它的开头要么从 nums[i] 开始要么接在以 nums[i-1] 结尾的某个子数组后面。而“以 nums[i-1] 结尾的所有子数组”里面和最大的那个就是 dp[i-1]。任何其他以 nums[i-1] 结尾的子数组和都不如 dp[i-1] 大接上 nums[i] 之后自然也不是最优。因此转移方程是dp[i] max(nums[i], dp[i-1] nums[i])这个式子还可以写成等价形式dp[i] max(0, dp[i-1]) nums[i]但这里有个重要区别如果 max(0, dp[i-1]) 在 dp[i-1] 为负数时取了 0含义是“前面的不要了从当前元素重新开始”。这个等价写法更直观但要注意它隐含的前提是子数组可以为空而我们题目要求至少有一个元素所以在最终答案里不能简单地直接取 max(0, dp[i])。用前一种写法 dp[i] max(nums[i], dp[i-1] nums[i]) 更稳妥因为它即使在全负数的情况下也能正确工作。2.3 动态规划三要素有了状态定义和转移方程这道题的动态规划三要素就齐了初始状态dp[0] nums[0]因为以第一个元素结尾的子数组只有它自己。状态转移dp[i] max(nums[i], dp[i-1] nums[i])。最终答案所有 dp[i] 中的最大值即 max(dp[0..n-1])。我之所以强调“所有 dp[i] 的最大值”而不只是 dp[n-1]是因为最大子数组可能在数组中间某个位置就已经出现不一定非要包含最后一个元素。比如 [5, -10, 6]dp[2] 是 -4但答案是 dp[0] 5。很多人第一次写的时候直接返回 dp[n-1]结果在大型数据里莫名其妙错几个 case原因就在这。3. C实现与细节优化3.1 基础版实现清晰直观的O(n)空间版本根据上面的状态定义和转移方程最容易理解的 C 实现是维护一个 dp 数组。代码如下#include vector #include algorithm using namespace std; int maxSubArray(vectorint nums) { int n nums.size(); if (n 0) return 0; // 具体按题目要求处理 vectorint dp(n); dp[0] nums[0]; int ans dp[0]; for (int i 1; i n; i) { dp[i] max(nums[i], dp[i-1] nums[i]); ans max(ans, dp[i]); } return ans; }这个版本的时间复杂度是 O(n)空间复杂度是 O(n)。逻辑非常直白适合初学者理解。每一步 dp[i] 都在用前一步 dp[i-1] 的结果做决策符合动态规划递推的核心思路。3.2 空间优化滚动变量与Kadane算法观察转移方程可以发现dp[i] 只依赖 dp[i-1]当前状态只跟前一个状态有关。这给了我们很大的空间优化空间不需要把整个 dp 数组都存下来只需要两个变量滚动更新就够了。int maxSubArray(vectorint nums) { int n nums.size(); if (n 0) return 0; int curSum nums[0]; // 相当于 dp[i] int ans nums[0]; // 最优答案 for (int i 1; i n; i) { curSum max(nums[i], curSum nums[i]); ans max(ans, curSum); } return ans; }这就是大名鼎鼎的 Kadane 算法。它本质上和上面的动态规划完全等价只是省掉了数组。空间复杂度从 O(n) 降到 O(1)处理超长数组比如几百万个元素的时候内存占用可以忽略不计。实际面试中绝大多数人写的是这个滚动版本因为它既简洁又高效。注意 curSum 这个名字起的很形象它记录的是“当前这一步以当前元素结尾的最大子数组和”。每次迭代它都在更新自己的含义这就是滚动变量。3.3 复杂度分析与初始化细节时间上我们只遍历了一次数组每一轮做常数次操作所以时间复杂度是 O(n)。空间上只用了两个 int 变量所以空间复杂度是 O(1)。初始化这个地方有个细微的点curSum 和 ans 都初始化为 nums[0]而不是 0。如果初始化为 0那么当数组全为负数时curSum 第一轮就可能被错误地计算。比如数组是 [-3, -5]初始化为 0 的话curSum max(-3, 0 (-3)) -3ans max(0, -3) 0最终答案是 0但这显然是错的因为题目要求至少选一个元素。尽管这种错误在主流的 LeetCode 版本里不容易触发因为很多人默认答案至少 0但遇到全负数用例就会翻车。所以初始值必须来自数组的真实元素而不是一个武断的 0。4. 常见问题与排查技巧实录4.1 边界情况空数组、单元素数组、全负数我在写题和帮别人 review 代码时发现这里有三个高频坑。第一个是空数组。大部分题目的约束是数组至少有一个元素但保险起见还是应该处理 n 0 的情况。你可以返回 0、返回 INT_MIN 或者抛出异常具体看题目的要求但不要让它静默地访问 nums[0] 导致越界崩溃。第二个是单元素数组。比如 [5]正确的答案是 5。如果代码里循环从 i1 开始ans 初始化为 nums[0]那么循环根本不会执行直接返回 5没问题。但如果你写成 ans 初始化为 0那当数组是 [-5] 时就会返回 0错了。所以牢记ans 和 curSum 都初始化为 nums[0]。第三个是全负数数组。以 [-8, -3, -1, -6] 为例正确做法是选 -1 作为最大子数组和。Kadane 算法的流程是curSum -8ans -8i1curSum max(-3, -8 (-3)) -3ans max(-8, -3) -3i2curSum max(-1, -3 (-1)) -1ans max(-3, -1) -1i3curSum max(-6, -1 (-6)) -6ans max(-1, -6) -1最终答案是 -1完全正确。关键在于每次遇到负数时curSum 都会在同 nums[i] 的比较中重新调整。负数会让“接着前面”的方案变得更糟但如果前面已经比当前元素都差那果断从当前元素重新开始。4.2 整数溢出隐患当数组元素范围较大比如元素是 int 最大值附近的正数连续累加时中间结果可能超出 int 范围。以数组 [2147483647, 2147483647] 为例理论最优答案是 4294967294但 int 根本存不下。实际上这可能触发带符号整数溢出导致结果变成负数。在面试和竞赛中应对方案是要么用 long long 类型存储 curSum 和 ans要么先确认题目给定的数组范围。如果是刷题场景我建议直接用 long long 做中间变量最后转回 int。虽然 LeetCode 53 的原题通常不会给这么极端的用例但保留这个习惯能规避很多隐藏的 overflow bug。long long maxSubArray(vectorint nums) { int n nums.size(); if (n 0) return 0; long long curSum nums[0]; long long ans nums[0]; for (int i 1; i n; i) { curSum max((long long)nums[i], curSum nums[i]); ans max(ans, curSum); } return ans; }别小看这个改动真实生产环境里数据总量往往超出直觉防御性编程很重要。4.3 打印具体子数组记录左右端点很多面试官在让你求最大值之后会追加一问能不能把对应的子数组本身输出这个需求在实际业务里也很常见比如要定位是哪一段时间段贡献了最大收益。做法是额外记录两个变量 start 和 end以及一个临时起始位置 tmpStart。每当 curSum nums[i] 比 nums[i] 大时说明我们延续了之前的子数组tmpStart 不变当 nums[i] 更大时说明要重新开始了tmpStart 更新为 i。当 ans 被刷新时同步更新 start tmpStartend i。完整代码如下vectorint maxSubArrayWithIndices(vectorint nums) { int n nums.size(); int curSum nums[0]; int ans nums[0]; int tmpStart 0; int start 0, end 0; for (int i 1; i n; i) { if (nums[i] curSum nums[i]) { // 重新开始更优 curSum nums[i]; tmpStart i; } else { curSum nums[i]; // 延续之前的子数组 } if (curSum ans) { ans curSum; start tmpStart; end i; } } return vectorint(nums.begin() start, nums.begin() end 1); }这里我用了分散的比较逻辑而不是直接一行 curSum max(...)目的是为了同步追踪 tmpStart。你也可以用三目运算符但注意优先级。4.4 封装、测试与代码风格实际开发中不会只写一个孤零零的函数通常要搭配完善的测试用例。我建议至少覆盖以下几类普通正负混合数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]期望 6。全负数[-8, -3, -1, -6]期望 -1。单个元素[5] 和 [-5]。全部为正数[1, 2, 3, 4]期望 10整个数组本身就是最优解。全零数组[0, 0, 0]期望 0。用一个简单的表格总结这几类测试用例测试数组期望输出容易踩的坑[-2, 1, -3, 4, -1, 2, 1, -5, 4]6以为 dp[n-1] 就是答案[-8, -3, -1, -6]-1初始化为 0 导致错误输出 0[5]5初始化为 0 导致单负数失败[1, 2, 3, 4]10restart 逻辑混乱导致漏掉整个数组[0, 0, 0]0空子数组判定问题这些用例跑通之后这个函数基本就稳了。5. 进阶扩展与变体5.1 环形数组的最大子数组和LeetCode 918 是最大子数组和的环形版本给定一个整数数组 nums 表示环形数组要求返回最大可能子数组和。所谓环形就是数组首尾相连子数组可以跨越原来的边界。处理环形的经典思路是“去环”问题的答案要么来自普通数组内部的最大子数组和不跨边界要么来自跨越边界的部分。而跨越边界的部分等于整个数组的总和减去数组内部的“最小子数组和”。具体来说情况一不跨越边界直接跑 Kadane 求 maxSum。情况二跨越边界总和不包括中间某一段最小子数组即 sum - minSum其中 minSum 是数组的最小子数组和。最终答案是 max(maxSum, sum - minSum)。但这个做法有一个关键坑如果数组全为负数比如 [-3, -2, -5]sum 为负sum - minSum 会等于 0 左右甚至是一个空的子数组但实际正确的最大子数组应该是数组中的最大值 -2。所以全负数时要特判直接返回数组中的最大值。这是环形版本最经典的边界问题。具体 C 代码int maxSubarraySumCircular(vectorint nums) { int total 0; int maxSum INT_MIN; int curMax 0; // 这里用0初始化是为了方便全负数特判 int minSum INT_MAX; int curMin 0; for (int num : nums) { total num; curMax max(num, curMax num); maxSum max(maxSum, curMax); curMin min(num, curMin num); minSum min(minSum, curMin); } if (maxSum 0) return maxSum; // 全负数情况 return max(maxSum, total - minSum); }注意这里 curMax 用 0 初始化其实并不影响 maxSum 的正确性因为只要数组不全为负第一次迭代 curMax 就会更新成非负的某个值。最后全负数检测靠的是 maxSum 0。5.2 分治解法另一种角度除了动态规划最大子数组和还有一个经典的分治做法把数组从中间分成左右两半最大子数组要么完全在左边要么完全在右边要么跨越中点。前两种递归求解最后一种从中间向两边扩展分别找最大后缀和与最大前缀和相加。int maxCrossSum(vectorint nums, int left, int mid, int right) { int leftSum INT_MIN; int sum 0; for (int i mid; i left; i--) { sum nums[i]; leftSum max(leftSum, sum); } int rightSum INT_MIN; sum 0; for (int i mid 1; i right; i) { sum nums[i]; rightSum max(rightSum, sum); } return leftSum rightSum; } int maxSubArrayDivide(vectorint nums, int left, int right) { if (left right) return nums[left]; int mid left (right - left) / 2; int leftMax maxSubArrayDivide(nums, left, mid); int rightMax maxSubArrayDivide(nums, mid 1, right); int crossMax maxCrossSum(nums, left, mid, right); return max({leftMax, rightMax, crossMax}); }这个做法复杂度是 O(n log n)空间是递归栈的 O(log n)。它不如 Kadane 高效但它体现的分治思想对后续学习归并排序、树形分治问题很有帮助。面试中如果被要求“换一种解法”能熟练写出这个分治版本会加不少印象分。5.3 统计最大子数组的个数有些变体会问具有最大和的子数组一共出现了几个这种题目通常要求找所有不同起止位置的子数组。做法是在 Kadane 循环过程中同时维护一个 count 数组。curSum 转移时分别计数当 dp[i-1] nums[i] nums[i]说明最优方案来自延续此时以 nums[i] 结尾的最大子数组个数和以 nums[i-1] 结尾的个数一样当 dp[i-1] nums[i] nums[i]说明只有从 nums[i] 重新开始这一种方案当两者相等时方案数是两者之和。这个变体考察的是对转移方程的深层理解面试中能流畅回答“为什么两种选择相等时需要累加”基本就吃透了这一题。5.4 二维最大子矩阵如果把一维数组扩展到二维矩阵问题变成求最大和的子矩阵。这个题本身不直接用一维 Kadane但它的核心套路是把二维压成一维枚举矩阵的上下边界然后对每一列求和得到一个一维数组再对这个一维数组跑 Kadane。总复杂度 O(n^2 * m)。这个技巧在竞赛里叫“降维打击”是二维 DP 预处理的高频方法强烈建议顺手把这道扩展题也刷了。5.5 相关问题买卖股票的最佳时机最大子数组和的思路还被大量复用在其他问题里。“买卖股票的最佳时机”系列中最大利润本质上可以被建模成相邻天价格差的最大子数组和。把每天的差值 diff[i] prices[i] - prices[i-1] 求出来然后跑 Kadane得到的就是最优单次买卖的利润。这个转换非常巧妙面试官很爱考掌握了最大子数组和等于把一道股票题也顺带掌握了。6. 从刷题到实际工程动态规划思维的落地说实话在实际的后端开发里一个数组可能来自传感器采集、行情数据、日志统计等场景。“最大子数组和”的抽象能力在于任何需要找连续区间最大贡献量的问题本质上都在求某种“连续增益的最大累计值”。比如统计某段时间内净流入最高的连续日期、找出网络流量中持续最大的突发区间用 Kadane 都能做。动态规划的核心其实不是背公式而是理解“以 i 结尾”这个状态的精妙之处。它把一个全局最优化问题活生生地拆成可以一步步递推的局部最优问题。这种“看屁股不看头”的思考方式在后面学习最长递增子序列、编辑距离、背包问题的时候会一遍又一遍地出现。就我个人的体会来说每次给学生讲动态规划算法我都会先讲最大子数组和因为它足够简单却又完整地包含了定义状态、推导转移方程、初始化、确定遍历顺序的全过程。把这题的逻辑在纸上推导三遍比盲目刷十道难题有效得多。如果看完这篇文章你觉得有点懂了建议立刻关掉网页用纯手写的方式把 Kadane 代码敲一遍再去 LeetCode 提交试试。那种自己跑通的成就感比看任何教程都来得真。