最大连续子序列和问题在算法设计与分析课程里几乎是个必考的存在期末编程题喜欢考各种复试机试喜欢考面试算法题也喜欢考。一个看似简单的“给一串整数找连续一段让和最大”却能同时讲清楚蛮力法、分治法、动态规划法三种完全不同级别的思路——这也是很多同学第一次直观感受到“同一个问题算法的差距可以这么大”的地方。这篇文章我就把这三种做法完整拆开讲。会用可运行的C代码、逐步推导的复杂度分析以及我在实际写这些算法时踩过的细节坑。适合正在准备算法设计与分析期末考试、或者刚开始接触分治和动态规划、想一次性把三种方法串起来理解的人。1. 开胃菜蛮力法也有两重境界先跑通再优化1.1 先把问题定义清楚子序列到底包不包括空集最大连续子序列和输入是一个整数序列比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]要求找出一段连续的元素使它们的和最大。在这个例子里答案是[4, -1, 2, 1]和为 6。这里有个容易让人纠结的点子序列能不能是空集纯数学定义里空集的和是 0如果整个序列全是负数比如[-3, -5, -2]非空的最大子序列就是-2而允许空子序列的话答案是 0。绝大多数课程和面试题默认“子序列非空”也就是至少要选一个元素。动手写代码前一定要先确认这个约定否则后面全负序列的测试用例会让你和标准答案对不上。界定了这一点再看蛮力法就顺理成章。所谓蛮力就是枚举所有可能的起点和终点把每一种连续片段都算一遍和取最大值。这个思路没什么门槛但它是一切优化方案的起点。1.2 O(n³)朴素三重循环与第一次优化方向最朴素的写法就是三重循环。第一层枚举起点i第二层枚举终点j第三层从i到j累加求和。int maxSubarrayBrute(vectorint nums) { int n nums.size(); int best INT_MIN; for (int i 0; i n; i) { for (int j i; j n; j) { int sum 0; for (int k i; k j; k) { sum nums[k]; } best max(best, sum); } } return best; }这段代码思路非常简单几乎不会出错唯一要注意的是第三层循环的起点是i不是 0。如果从 0 累加到j算出来的就不是i到j的和了。还有初始化best要用INT_MIN而不是 0否则遇到全负序列时答案会被错误地固定成 0。三重循环的问题在于它做了大量重复计算。外层i0时已经把从 0 到所有j的和算了一遍i1时又把从 1 到j的和重算一遍。这些内部的和明明可以递推出来不需要每次重新累加。1.3 去掉最内层循环O(n²)枚举起点法所以第一次优化是去掉最内层循环。固定起点i后终点j从i一路往右移动同时维护一个累加变量sum每加入一个nums[j]就更新一次答案。int maxSubarrayOn2(vectorint nums) { int n nums.size(); int best INT_MIN; for (int i 0; i n; i) { int sum 0; for (int j i; j n; j) { sum nums[j]; best max(best, sum); } } return best; }这样复杂度从 O(n³) 降到 O(n²)。在 n1000 左右的规模内两种写法跑起来差别还不明显但 n 到 5000 以上三重循环就开始明显卡顿。蛮力法的意义不在于效率而在于它是所有正确性验证的基准。后面写分治和 DP我都会先用小规模的随机数拿 O(n²) 的结果去对拍确认新算法没写错。2. 分治法问题一分为二答案变成三种情况2.1 为什么用中线切开就能覆盖所有情况分治法的出发点很简单把数组从中间切成两半任何一段连续子序列要么完全落在左半部分要么完全落在右半部分要么跨越了中点、左右两边都占一部分。三种情况覆盖了所有可能性不存在第四种。于是问题被拆成三个子问题左半的最大子序列和、右半的最大子序列和、跨中点的最大子序列和。前两个分别递归求解最后一个单独处理三者取最大。这种“一分为二、分类讨论”的思想是分治法最典型的套路值得反复体会。这里有一个关键认知分治不是“把数组切成两半后递归求两边答案”就结束了。如果你只比较左右两半递归结果会漏掉跨中点的那些情况。比如全正数组[1, 2, 3, 4]左半最大是 3右半最大是 4但真正答案 10 横跨中点。所以“合并”这一步才是分治法最容易出错的地方也是考核的重点。2.2 跨中点序列的合并计算向左、向右各扫一遍很多人写分治时卡在“跨中点的最大子序列和怎么求”。关键在于既然这段子序列跨过中点它一定包含nums[mid]和nums[mid1]这两个相邻元素。剩余部分可以完全落在左侧、也可以完全落在右侧但不能左右两边都取之后再折返那样就不是连续的一段了。所以做法是从mid开始向左扫找从某一处到mid的最大后缀和从mid1开始向右扫找从mid1到某一处的最大前缀和。两者相加就是跨越中点的最优值。int maxCrossSum(vectorint nums, int left, int mid, int right) { int leftSum INT_MIN, 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; }这里有个很容易犯的错向左扫描时总和一旦变负就清零重来。这其实是 Kadane 算法的思路不能直接用在跨中点的合并上。我们要的是“从任意位置开始到mid为止”的最大值哪怕累加过程中某一段是负数也不影响继续累加后面的元素只要每次累加后取max就行。不需要清零也不能清零。2.3 递归代码实现与复杂度推算有了合并函数完整的递归求解就清晰了int maxSubarrayDivide(vectorint nums, int left, int right) { if (left right) { return nums[left]; } int mid left (right - left) / 2; int leftAns maxSubarrayDivide(nums, left, mid); int rightAns maxSubarrayDivide(nums, mid 1, right); int crossAns maxCrossSum(nums, left, mid, right); return max({leftAns, rightAns, crossAns}); }递归基是left right此时只有一个元素直接返回该元素即可。这里不需要处理left right的情况因为我们的递归切割方式不会出现空区间。复杂度很容易推。合并的扫描需要 O(n) 时间递归把问题分成两半所以 T(n) 2T(n/2) O(n)由主定理得到 O(n log n)。和 O(n²) 相比n 到 10 万时O(n log n) 大约只要百万级别的操作而 O(n²) 要百亿级别差距是决定性的。递归实现还有一个细节要留意mid left (right - left) / 2比(left right) / 2更安全能避免left right溢出。虽然本题数据规模不太会触发但养成这个习惯没有坏处。3. 动态规划把“以i结尾”的局部最优串起来3.1 状态定义是最大难关不是“前i个”而是“以i结尾”动态规划最大的难点往往不是转移方程而是状态定义。最大连续子序列和我第一次学的时候总想着用dp[i]表示“前 i 个元素中最大子序列和”结果转移起来特别别扭因为前 i 个元素的最大值不一定能延续到第 i1 个元素信息不够。正确的定义是dp[i]表示以第 i 个元素结尾的最大连续子序列和。也就是说这一段必须包含nums[i]并且是它作为最后一段时能拿到的最大和。有了这个定义转移就很自然了。dp[i]只有两种来源要么把nums[i]接到dp[i-1]代表的那个最优子段后面结果就是dp[i-1] nums[i]要么干脆不接从nums[i]重新开始一段结果就是nums[i]。取较大者。用公式写就是dp[i] max(dp[i-1] nums[i], nums[i])最终答案不是dp[n-1]而是所有dp[i]中的最大值。为什么因为以 i 结尾的子段可以是任何一段正确答案可能出现在任意位置。比如[1, -10, 5]dp[2] 5但最大值也是 5看起来碰巧一样再看[2, 3, -10, 4]dp[3] 4但实际最大值是dp[1] 5。所以最后一定要遍历一遍dp数组取最大值。3.2 从dp数组到滚动变量空间复杂度降到O(1)先写一个朴素版本开一个dp数组逐个填填完后再取最大值。int maxSubarrayDP(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int best dp[0]; for (int i 1; i n; i) { dp[i] max(dp[i - 1] nums[i], nums[i]); best max(best, dp[i]); } return best; }这段代码的时间复杂度是 O(n)空间复杂度 O(n)。但很快就能发现dp[i]只依赖dp[i-1]和更早的状态没有关系。于是可以只用两个变量prev保存dp[i-1]best保存到目前为止的最大值。int maxSubarrayDPOptimized(vectorint nums) { int n nums.size(); int prev nums[0]; int best prev; for (int i 1; i n; i) { prev max(prev nums[i], nums[i]); best max(best, prev); } return best; }这就变成了很多面试题标准答案的样子O(n) 时间、O(1) 空间而且代码非常稳定。这个优化手段很常见当转移方程只依赖前一个状态时数组就可以压缩成滚动变量。3.3 这个定义为什么是对的无后效性一次讲透有些同学看到这个 DP 写法总觉得像“玄学”其实它之所以正确依靠的是局部最优的可延续性。dp[i-1]如果小于 0说明前面那段再长接到nums[i]前面只会拖累nums[i]所以不如从nums[i]重新开始。如果dp[i-1]大于等于 0把它接上一定不亏因为任何以nums[i]为结尾的子段要么包含前面一段、要么不包含包含时能带来的最好前缀就是dp[i-1]。这种“决策只关心上一步的最优值”的性质就是动态规划里的无后效性。当前状态一旦确定就不关心它是怎么来的后续决策只依赖这个状态值本身。理解了这个以后再看到类似的“最大子数组和”“最长上升子序列”就不会被转移方程绕晕了。4. 三种方法放到同一条数据上实测复杂度之外还有细节4.1 复杂度对比与运行时间感受把几种方法放在一张表里方法时间复杂度空间复杂度实现难度适用数据规模蛮力三重循环O(n³)O(1)最低n≤200左右蛮力枚举起点O(n²)O(1)低n≤5000左右分治法O(n log n)O(log n) 递归栈中n≤10⁶级别动态规划O(n)O(1)中任何常规规模这个表也在提醒一个很现实的问题考试和面试里数据范围本身就是提示。题目说n≤1000那 O(n²) 的写法完全能过不必强行上 DP。题目说n10⁵如果你还在写 O(n²)超时是必然的。我在本机用随机数据测过 n10⁵ 时几种方法的耗时O(n²) 大概在数秒到十几秒O(n log n) 在几十毫秒量级O(n) 几乎瞬时。读者自己测试时可以生成一个随机数组先用 O(n²) 的结果当基准再用分治和 DP 的结果去对拍这是最稳的验证手段。4.2 全负序列、单个元素与整数溢出的边界问题这三种方法都容易踩几个坑。第一全负序列。如果输入是[-3, -5, -2]正确答案是 -2。如果初始化best 0就会输出 0错误。所以初始化要用INT_MIN或者直接取第一个元素。第二只有一个元素。此时分治递归直接走递归基返回DP 的prev和best都初始化为nums[0]循环从 1 开始能正确处理蛮力也能覆盖。真正容易出错的是你写的 DP 循环从 0 开始或者n0时直接访问nums[0]导致越界。写代码前想清楚输入是否保证非空。第三累加溢出。题目如果允许元素值很大比如 10⁹ 级别的 int累加和可能超过 int 的上限。C 里建议用long long保存中间结果和最终答案。虽然大多数课程作业不会卡这个但这是工程里真实存在的问题提前注意没有坏处。4.3 从期末考试和面试的出题视角看这道题从期末编程题的视角看这道题常见考法有三种一是直接让写出分治法或 DP 的完整代码这种最实在会写就是会写二是给一段代码填空缺经常会挖在跨中点合并那一段比如让你补全向左扫描的循环三是只问时间复杂度和思路需要你能熟练说出“分治 T(n)2T(n/2)O(n)O(n log n)”这种推导。面试的话我建议先背熟 DP 那个最短版本然后能讲清楚“为什么状态定义成以 i 结尾”。面试官通常不满足于“我背过这道题”他会追问状态转换的理由。能把这个讲明白这道题基本就是加分项。另外说一个很实用的小技巧如果题目要求同时输出最大和以及对应的子序列下标DP 版本要额外维护一个起点每次从新开始时更新起点每次更新答案时记录当前起点和终点。分治版本想找回下标会更麻烦因为跨中点的最优解要额外保存左右边界。这个扩展很多教材都不写但实际工程项目里拿到“哪一段最大”和拿到“最大是多少”一样重要。我个人在实际写这类题时的习惯是先用 O(n²) 的暴力写在草稿纸上确认题意再写正式算法最后用随机样例对拍一次。这样既保证正确性也避免算法写对了但题意理解偏了的尴尬。