1. 问题拆解先弄清最大子数组和到底在求什么1.1 题目定义与输入输出最大子数组和Maximum Subarray是动态规划里门槛最低、但思想含金量极高的一个问题。题目通常这样描述给定一个整数数组nums找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。比如nums [-2,1,-3,4,-1,2,1,-5,4]最大子数组是[4,-1,2,1]最大和是 6。这里有几个字眼要划重点。第一是“连续”意味着我们不能跳过元素去拼凑子数组在原数组里必须是挨着的一段。第二是“最少包含一个元素”这直接否决了空子数组作为答案的可能也决定了后面的初始化逻辑。第三是“最大和”注意是和值不是子数组本身题目要的是一个数值不是下标区间。这道题全网最常见的出处是 LeetCode 53 题难度标为Easy但实际面试里它出现频率极高而且经常作为动态规划入门的第一道例题。C 解法版本也很多从暴力三循环到分治再到 Kadane 算法性能差距可以拉到几百倍。本文就以 C 为主语言把这条思路从暴力一路优化到 O(n)把每一步为什么这样做讲透。1.2 为什么暴力解法不可行拿到题目最直觉的做法是枚举所有可能的子数组。三层循环第一层枚举起点第二层枚举终点第三层累加区间和。时间复杂度 O(n^3)如果优化一下在第二层循环里边扩边界边累加能把累计步骤省掉降到 O(n^2)。// 暴力解法 O(n^2) int maxSubArrayBruteForce(const 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; }这种写法在数组长度 1000 以内能跑但一旦 n 达到 10^5 甚至 10^6O(n^2) 就是灾难。10^5 个元素的平方操作是 10^10 次累加按每秒 10^8 次基本运算来算需要一百秒这在任何竞赛或面试场景里都是不可接受的。所以问题的核心不是“能不能求”而是“能不能用更聪明的办法求”。动态规划正是为这类问题准备的——它把大问题拆成结构相同的子问题用子问题的答案推导大问题的答案避免重复计算。最大子数组和的结构特殊性在于每个位置作为子数组结尾时答案只和它前一个位置的“最佳状态”有关这天然适合 DP 的状态转移。2. 动态规划核心思路状态定义和转移方程是怎么想出来的2.1 状态设计的核心洞察——以谁结尾很多初学者卡在“dp[i] 到底代表什么意思”这一步。这里有一个通用技巧对于子序列、子数组类问题优先考虑“以第 i 个元素结尾的”最优值。为什么因为连续性的约束决定了当前位置只能和它前面的位置衔接如果我们定义“以 i 结尾的最大子数组和”那么转移时只需要考虑 i-1 的状态不用回头看更早的位置——连续性的限制自然被状态定义消化掉了。定义dp[i]表示以nums[i]结尾的连续子数组的最大和。注意这个定义下的 dp 数组并不直接等于最终答案。最终答案需要在所有dp[i]里取最大值因为最大和子数组可能以任何一个位置结尾。比如[5, -10, 6]以 index 0 结尾的最大和是 5子数组[5]以 index 2 结尾的最大和是 6子数组[6]答案 6 来自 index 2不是最后一个位置。这个“dp 含义不等于答案”的设计是动态规划里非常典型的一类——状态定义服务于转移答案在状态集合上做归约。很多 DP 问题最长递增子序列、打家劫舍都有同样的模式读者可以放在一起对比记忆。2.2 转移方程推导与直觉解释有了dp[i]的定义下一步考虑dp[i]怎么从dp[i-1]推出来。以nums[i]结尾的子数组只有两种可能要么是[nums[i]]自己单独成一个子数组要么是把nums[i]接在以nums[i-1]结尾的子数组后面形成[某个子数组..., nums[i]]。第一种情况的和是nums[i]。第二种情况的和是dp[i-1] nums[i]因为“以 i-1 结尾的最大子数组”已经保证了前缀那一段在连续且和最大的前提下是最优的接上nums[i]并不破坏连续性。于是dp[i] max(nums[i], dp[i-1] nums[i])这个式子可以进一步化简为dp[i] max(dp[i-1], 0) nums[i]因为取最大值时等价于判断dp[i-1]是否大于 0如果前面的最佳累加是正数带上它如果是负数丢弃它重新开始。后一种写法在实现中更常见也更方便解释。这里有一个极其关键的直觉前缀是负的不如扔掉重来。假设你手里有一段子数组的和是-3现在下一个元素是5-3 5 2明显不如直接从 5 开始。这个逻辑放在生活中也很好理解——你背着一个亏损的项目继续向前通常不如止损后重新起步。动态规划的分析不做这种“赌未来会反弹”的情感判断它只做严格的大小比较。初始化就是dp[0] nums[0]因为以第一个元素结尾的子数组只有一个就是它本身。答案从max(dp[0], dp[1], ..., dp[n-1])中取。2.3 与贪心直觉的关系很多讲 Kadane 算法的资料会说“遍历时维护当前和如果当前和变成负数就清零”这本质上就是贪心视角。但严格来说Kadane 算法是动态规划的空间优化版本它的正确性来源于上面这个转移方程而不是直觉本身。理解成 DP 再看这个“清零”操作会清楚很多清零是在 max 比较中选择了nums[i]而不是dp[i-1] nums[i]是状态转移的自然结果不是什么特别的贪心策略。3. C 实现从朴素版本到满分解法3.1 基础 DP 版本的完整实现先把最直白的版本写出来开一个dp数组逐个位置计算最后取最大值。#include vector #include algorithm #include climits int maxSubArray(const vectorint nums) { int n nums.size(); 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; }这段代码的优点是逻辑清晰和转移方程一一对应教学价值高适合放在博客里给初学者看。所有中间状态都保存在dp数组里如果需要事后回溯“具体哪一段是最大子数组”这些状态的留存在后面会派上用场。这里注意一个细节ans不能初始化为 0而要初始化为dp[0]也就是nums[0]。如果数组全是负数例如[-3, -1, -2]正确答案是-1不是0。把ans初始化为 0 是一个极其常见的错误后面第 4 章会专门展开。3.2 空间优化滚动变量版本观察转移方程dp[i] max(nums[i], dp[i-1] nums[i])可以发现dp[i]在计算时只依赖dp[i-1]完全没有必要把整个数组存下来。用一个变量记录“以当前位置结尾的最大和”滚动更新即可。int maxSubArrayOptimal(const vectorint nums) { int cur 0; // 当前以 i 结尾的最大和 int ans INT_MIN; for (int num : nums) { cur max(num, cur num); ans max(ans, cur); } return ans; }这段代码有个很多人看不透的细节cur初始化为 0ans初始化为INT_MIN循环体里先更新cur再更新ans。这样即使数组只有一个元素第一轮循环也能把ans设置成正确的值。如果cur初始化为 0ans初始化为 0全负数数组会返回错误结果。理解了这个顺序你就知道为什么很多教科书代码第一眼看起来别扭但实际是对的。空间复杂度从 O(n) 降到 O(1)时间复杂度 O(n)。这个版本也叫 Kadane 算法是面试和竞赛的标准答案。如果需要更严谨地处理空数组的情况可以在函数开头加一个if (nums.empty()) return 0;不过 LeetCode 原题保证数组非空面试时可以和面试官确认输入约束。3.3 使用 STL 的两种风格C 的迭代器风格和下标风格都可以写。下面这个版本用了范围 for 循环代码最简洁int maxSubArraySTL(const vectorint nums) { int cur 0, ans INT_MIN; for (int x : nums) { cur std::max(x, cur x); ans std::max(ans, cur); } return ans; }还有更“现代 C”的写法用std::reduce配合 lambda但可读性其实不如普通循环不推荐在入门阶段这么写。算法题优先保证可读性和无歧义炫技性的 STL 组合反而容易让读代码的人困惑。三种实现数组版、滚动变量版、STL 版的差异主要在空间和代码风格核心逻辑完全一致。面试时推荐先写滚动变量版因为代码短、不容易错如果面试官追问“能否看出这个子数组的起点终点”再补充数组版或者额外维护起止下标。4. 常见错误与调试经验4.1 边界情况全负数、单元素、空数组全负数数组是最大子数组和最经典的陷阱。[-3, -1, -2]的正确答案是-1因为题目要求子数组至少包含一个元素我们只能选最大的负数不能选空数组的和 0。对应到代码里就是ans的初始化问题。如果你把ans初始化为 0全负数数组会错误地返回 0。我做题时就踩过这个坑当时自信满满提交WA 了一个测试点排查半天发现是初始化的问题——这类边界设计的错误编译器不会报错逻辑也很难一眼看出最好的办法是在写完代码后手动跑两个用例全正数、全负数都对了基本就稳了。单元素数组[5]返回 5[-5]返回 -5。这两种情况在任何正确版本里都应该直接返回唯一元素因为循环只跑一次。如果代码里先对n 0做特殊处理别忘了n 1不需要单独处理普通循环天然覆盖。空数组属于题目约定之外的情况实际环境中可能遇到。有人喜欢返回 0有人喜欢抛异常或返回INT_MIN。不同的选择各有道理但必须在函数注释里写清楚约束否则调用方会困惑。4.2 整数溢出与数据范围dp[i] max(nums[i], dp[i-1] nums[i])中的dp[i-1] nums[i]可能溢出。如果数组元素是int类型最大绝对值到2^31-1两个这样的数相加就超出int范围产生未定义行为。解决方式有两种一是使用long long作为累加和类型二是根据题目约束判断溢出是否可能出现。刷题平台通常给的nums[i]范围在[-10^4, 10^4]之间n 最大 10^5总和最大 10^9还在int范围内。但竞赛题如果数值给到10^9量级累加就可能破界使用long long更保险。long long maxSubArrayLL(const vectorint nums) { long long cur 0, ans LLONG_MIN; for (int num : nums) { cur maxlong long(num, cur num); ans max(ans, cur); } return ans; }注意maxlong long的写法避免numint 类型和cur numlong long 类型之间的隐式转换歧义。新手容易在这里踩坑用模板参数显式指定比较类型代码更稳。4.3 混淆状态定义导致逻辑错误一个常见的错误版本是dp[i]定义为“前 i 个元素中最大子数组和”而不是“以 i 结尾的”然后转移写成dp[i] max(dp[i-1], dp[i-1] nums[i])。这个版本在正数数组上碰巧正确但遇到负数数组就会出错。比如[2, -3, 4]按这个错误公式走dp[2] max(2, 2-3) 2接着dp[3] max(2, 24) 6碰巧算对了但换个用例[2, -5, 4]dp[2] 2dp[3] max(2, 6) 6仍然是 6好像又对了。再试[2, 3, -100, 5]错误公式到dp[3] max(3, 3-100) 3然后dp[4] max(3, 35) 8实际答案应该是 5子数组[5]错误。因为前 i 个的最佳区间不一定以 i 结尾强行拼接会破坏连续性导致结果虚高或虚低根本原因是没有把“连续”这个约束编码进状态定义。这类错误调试起来很费劲因为有时候碰巧输出正确有时候又不正确。我的经验是宁可花一分钟在白纸上手推一遍状态转移也不要直接上手改代码盲猜。写 DP 之前先问问自己三个问题——状态代表什么转移怎么保证约束答案从哪取三个问题都想清楚了再动键盘。4.4 调试技巧打印 dp 数组对于 DP 问题调试时打印 dp 数组是最有效的手段。C 实现里可以临时加一段输出for (int i 0; i n; i) { cout dp[ i ] dp[i] endl; }用[-2, 1, -3, 4]跑一遍正确的 dp 序列应该是[-2, 1, -2, 4]。如果在某个位置出现不符合直觉的值检查转移方程里那个max的参数有没有写反或者是不是拿nums[i]和dp[i-1]比较而不是和dp[i-1] nums[i]比较。这类句式错误在 C 中不报错只能靠打印结果发现。5. 延伸思考从一行代码到一类问题5.1 如何返回最大子数组本身有时候面试官会追加一句“能不能顺便返回最大子数组的起始和结束下标”这需要我们在滚动更新的同时记录边界。维护两个变量start和end每当cur被更新为num即丢弃之前的负数前缀时说明一个新的子数组从当前位置开始每当ans被更新为新的cur时记录当前的结束位置。vectorint maxSubArrayWithIndices(const vectorint nums) { int cur 0, ans INT_MIN; int tempStart 0, start 0, end 0; for (int i 0; i (int)nums.size(); i) { if (cur 0) { cur nums[i]; tempStart i; } else { cur nums[i]; } if (cur ans) { ans cur; start tempStart; end i; } } return {ans, start, end}; }这段代码里cur 0的判断和max写法是等价的但用分支写更方便记录起点。注意tempStart只在cur被重置时更新一旦ans在后续位置被刷新就使用对应的tempStart。这个逻辑在纸面上画一遍就知道为什么要分成两个变量直接把这些信息存在 dp 数组里会更直观但占空间。5.2 扩展到环形数组如果题目改成“数组可以首尾相接成环求最大子数组和”问题就复杂了一步。环形数组意味着最大和子数组要么出现在正常线性区间要么跨越首尾边界。跨越边界的场景等价于“整个数组的和减去最小子数组和”。理由很简单首尾相接后剩下的部分必然是一段连续区间和最大等价于被排除的区间和最小。于是算法是环形最大和 max(线性最大和, 总和 - 线性最小和)还需要处理特殊情况如果所有元素都是负数线性最大和是最大的负数而“总和 - 最小和 总和 - 总和 0”这种情况应该返回线性最大和否则会错误返回 0。这个坑比一维版本更隐蔽值得单独强调。int maxSubarraySumCircular(const vectorint nums) { int total 0; int curMax 0, maxSum INT_MIN; int curMin 0, minSum INT_MAX; for (int num : nums) { total num; curMax max(num, curMax num); maxSum max(maxSum, curMax); curMin min(num, curMin num); minSum min(minSum, curMin); } return maxSum 0 ? max(maxSum, total - minSum) : maxSum; }这是 LeetCode 918 题的标准解法一次遍历同时维护最大值和最小值时间复杂度 O(n)空间 O(1)。理解了一维版本这个扩展版本其实只差一个“总和减去最小和”的视角转换。5.3 从一维到二维最大子矩阵问题把一维数组扩展到二维矩阵问题变成“找出和最大的子矩阵”。经典做法是枚举上下边界把每一列的和压缩成一个一维数组然后跑 Kadane。int maxSumSubmatrix(const vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); int ans INT_MIN; for (int top 0; top m; top) { vectorint colSum(n, 0); for (int bottom top; bottom m; bottom) { for (int col 0; col n; col) { colSum[col] matrix[bottom][col]; } int cur 0, best INT_MIN; for (int sum : colSum) { cur max(sum, cur sum); best max(best, cur); } ans max(ans, best); } } return ans; }这个版本的时间复杂度是 O(m^2 * n)。上下边界的枚举是 O(m^2)每一轮内部对压缩后的一维数组跑 Kadane 是 O(n)整体可行。矩阵维度几百以内都能接受如果维度上千需要考虑更高级的优化但一维 Kadane 的功底仍然是基础中的基础。最大子数组和的价值正在于此从一维到二维从线性到环形从求值到追踪区间它始终是那个最核心的模版。很多看起来完全不同的题比如股票买卖的最佳时机、连续子数组的最大乘积剥开外壳之后状态转移的思想骨架都和它惊人地相似。我在实际做算法题时最大的体会是最大子数组和这道题值得每个学 C 的人亲手推一遍全过程——暴力代码、dp 数组版本、滚动变量版本、带下标的版本、环形扩展版本逐个实现一遍。这个过程会让你真正理解“状态设计”是怎么回事远比自己对着题解抄十遍更有效。踩过无数次ans初始化为 0 的坑之后我现在写 DP 第一件事就是问边界全负数能过吗单元素能过吗想清楚了再提交省下的调试时间远比自己以为的要多。