在算法设计这门课里最大连续子序列和问题是最经典的入门题之一不管是期末考试、考研机试还是在线实训平台的作业它出现的频率都高得离谱。我记得当年第一次在头歌平台上刷到这道题时题目描述就一句话给定一个整数序列求其中连续子序列的最大和。看似简单但背后能挖出三种完全不同的算法思路蛮力法、分治法、动态规划法。这三种方法正好对应了算法设计课程里的三大核心板块而且复杂度从O(n^3)一路优化到O(n)整个过程就像看着一个粗糙的毛坯房被一步步精装修非常有代入感。这篇文章我就用自己的实际做题经历把这道题的三种解法从暴力到最优完整走一遍。不管你是刚接触算法的大一新生还是准备期末考的计算机系学生甚至是单纯想复习动态规划的社招党这篇内容都能给你实打实的帮助。我会把每种算法的思路推导、代码实现、复杂度分析、易错点全部分享出来最后还会聊聊我在在线判题平台上踩过的那些坑帮你避开同样的弯路。1. 问题定义与前置理解1.1 到底在求什么从“连续”两个字说起先统一一下问题的表述。给定一个整数序列a[1..n]我们要找到一个连续的子序列a[i..j]1 i j n使得这个子序列的元素之和最大输出这个最大值。这里有两个关键词需要划重点。第一个是“连续”这意味着你不能跳着选元素比如序列里第1个、第3个、第5个元素再加起来这不叫连续子序列这种操作是另一类问题。第二个是“子序列”它区别于“子串”但在这道题里因为要求连续所以它本质上是子串的概念。很多初学者在第一步就被这两个术语搞晕了后面对不上号。举个例子。输入序列[-2, 11, -4, 13, -5, -2]肉眼扫一遍最长的连续区间是下标2到4从第2个数到第4个数11 (-4) 13 20所以答案是20。但是如果你把范围扩展到整个数组和是 11-211-413-5-211比20小如果你只选最后一个或第一个那更小。这个问题就是要精确找到那个让和最大的连续窗口。这里有一个关键约定如果序列里全是负数结果怎么算常见的题目要求是返回最大的那个负数因为“空子序列的和为0”通常不被允许。但也有教材约定空子序列和为0得出答案0。我做题和考试时一般默认非空子序列也就是全负数时答案等于序列中的最大值。你在做题前一定要看清题目有没有特殊说明这种“约定差异”经常是在线判题WA错误答案的元凶。1.2 为什么这道题值得用三种方法做很多人学这道题有个误区觉得“反正动态规划最优直接看动态规划不就行了”。这种想法我特别理解但真的不建议这么干。因为这道题的教学价值恰恰在于同一个问题用不同的算法设计策略去思考得到的代码和复杂度完全不一样。蛮力法是“最笨但最直观”的思路它教会你怎么用枚举法暴力解决问题并且让你亲身体会到时间复杂度爆炸是怎么一回事。分治法教会你“大事化小、小事化了”的递归思维尤其是“跨越中点”的情况这是分治算法里一个非常经典的套路。动态规划法则展示了如何利用子问题的重叠性质用空间换时间、用状态转移方程一锤定音。如果你把这三种解法全部吃透你就等于打通了算法设计课程的任督二脉枚举、分治、动态规划。之后再遇到其他题目你至少能判断该往哪个方向思考。这也是我为什么把三种方法都讲一遍的原因而不是简单丢给你一个最佳解。2. 蛮力法从三重循环到两重循环的优化之路2.1 三重循环最原始的枚举思路蛮力法的核心思想就是“枚举所有可能的连续子序列分别求和取最大值”。这句话听起来简单但落到代码上有一个递进过程。第一次写这道题的时候我的思路是枚举子序列的起点i再枚举终点j然后把i到j之间的所有元素加一遍。这个逻辑用三重循环实现def max_subarray_bruteforce_v1(arr): n len(arr) 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): # 从 i 加到 j current_sum arr[k] max_sum max(max_sum, current_sum) return max_sum这个代码完全正确但它的时间复杂度是O(n^3)。我实测了一下当数组规模到1000左右时还能勉强跑完但到5000的时候就明显卡顿了超过10000基本等于死机。如果你在在线判题平台上提交这版代码大概率会收获一个“超时”的判决英语叫Time Limit Exceeded也就是常说的TLE。为什么这么慢因为为了求区间[i, j]的和我们每次都在循环里从头加一遍。如果已经有了[i, j-1]的和那么求[i, j]的和其实只需要再加一个arr[j]就可以。这个发现直接催生了第二版优化。2.2 两重循环去掉内层重复累加很多老师讲蛮力法时只讲到三重循环就跳到分治法了。但我觉得两重循环这个中间版本很有必要说因为它帮你理解“增量计算”的思想这个思想在后面的动态规划里也会出现。def max_subarray_bruteforce_v2(arr): n len(arr) max_sum float(-inf) for i in range(n): current_sum 0 for j in range(i, n): current_sum arr[j] # 利用上一次的计算结果 max_sum max(max_sum, current_sum) return max_sum这个版本的思路很朴素固定起点i然后终点j从i一直往右扫每扫过一个元素就把它累加到current_sum里然后更新答案。这样内层循环就只剩两重了时间复杂度从O(n^3)降到了O(n^2)。它的正确性靠的是“子区间逐步扩展”的逻辑区间[i, j]的和 区间[i, j-1]的和 arr[j]。这个公式虽然简单但它是后面动态规划里“前缀和思想”的雏形。代码里我用current_sum变量保存当前累加结果这比三重循环里每次重新计算省了整整一个数量级的时间。我可以给你一个直观感受。在我的笔记本电脑上n 10000的随机数组三重循环版本跑了大概2.8秒两重循环版本只跑了0.02秒左右。差距就是这么明显所以你千万别小看“去掉一层循环”这种优化。2.3 蛮力法的优缺点与适用场景蛮力法的优点说白了一个字稳。它逻辑直白不容易出错作为兜底方案特别合适。如果面试官让你“先讲思路再优化”你可以从蛮力法开始一边说一边推导展示你的思路演进过程。但它的缺点也很致命只适合数据规模极小的场景。比如n1000以内O(n^2)的算法也许能过但n10000以上就非常勉强了n100万时O(n^2)意味着10^12次运算在普通机器上要跑几十分钟直接不可用。我在实际写代码时蛮力法还有一个用途作为正确的基准答案。当我想验证分治法或动态规划法有没有写错时我会先生成一个随机数组把蛮力法的结果当标准答案再拿优化算法的结果去比对。这个“对拍”技巧在算法调试里非常实用后面我还会再提。3. 分治法把问题一分为二再处理跨过中线的情况3.1 分治模型的建立左半、右半、跨中分治法解决这个问题的思路是递归地“切”。把数组从中间位置mid分成左右两半那么最大连续子序列只可能有三种情况完全位于左半部分完全位于右半部分跨越中点也就是一部分在左半一部分在右半。对于前两种情况直接递归求子数组的最大值就行。对于第三种“跨中点”的情况我们不能简单地把左半最大值和右半最大值相加因为左右两个最大子序列并不一定连在一起。正确做法是从中点出发向左连续扩展找到左侧最大和从中点1出发向右连续扩展找到右侧最大和两个和相加得到跨中最大和。下面这个图可以帮你建立直观理解用文字模拟一下数组: [-2, 11, -4 | 13, -5, -2] mid2 (假设以索引2为界) 左半最大 11 右半最大 13 跨中最大 从11开始向左扩 - 11; 从13开始向右扩 - 13 但更优的是从-4往左扩到11 7, 从13往右扩到13 13 所以跨中最大 7 13 20你会发现跨中最大并不一定必须要包含mid本身而是“包含mid向两侧连续延伸的最大和”。这个细节特别容易错很多人误以为跨中最大就是左边最大加右边最大实际上必须保证从mid出发向两边连续延伸不能断开。3.2 分治法代码实现与递归深度分析这里我用Python写一份标准实现def max_subarray_divide(arr, left, right): # 递归终点区间只有一个元素 if left right: return arr[left] mid (left right) // 2 # 情况1最大子序列完全在左半边 left_max max_subarray_divide(arr, left, mid) # 情况2最大子序列完全在右半边 right_max max_subarray_divide(arr, mid 1, right) # 情况3跨中点的最大子序列 # 从中点向左扩展求包含mid的连续最大和 left_sum 0 left_cross_max float(-inf) for i in range(mid, left - 1, -1): left_sum arr[i] left_cross_max max(left_cross_max, left_sum) # 从中点1向右扩展求包含mid1的连续最大和 right_sum 0 right_cross_max float(-inf) for j in range(mid 1, right 1): right_sum arr[j] right_cross_max max(right_cross_max, right_sum) cross_max left_cross_max right_cross_max # 三种情况取最大值 return max(left_max, right_max, cross_max)调用时传入数组和下标max_subarray_divide(arr, 0, len(arr)-1)。这个递归过程的复杂度我帮你推导一下。假设问题规模为n递归式是T(n) 2 * T(n/2) O(n)其中2 * T(n/2)来自左右两个子问题O(n)来自跨中扫描。根据主定理Master Theorem这个递推式的解是O(n log n)。你可以理解为每一层递归都要把所有元素扫一遍跨中扫描合起来是O(n)总共递归了log n层所以总代价是O(n log n)。我在实际测试时发现n10万规模的数据分治法大概耗时几十毫秒比O(n^2)的两重循环快了太多但比后面要讲的O(n)动态规划还是要慢一些。这个对比也能直观说明好的算法设计哪怕思路再绕性能收益也是实实在在的。3.3 分治法的关键细节跨中线合并的方向分治法在考试里写代码最容易挂的地方就是跨中扫描的方向和起点。我当年第一次写的时候在左半部分扩展的循环里写成了for i in range(mid, left - 1, -1)一开始没注意边界写成了for i in range(mid, left, -1)结果漏掉了left这个端点答案在某些边界用例下就是错的。另一个更隐蔽的问题是跨中最大和必须同时包含mid和mid1吗严格来说它必须包含这两个位置中的至少一个吗其实定义是“跨越中点”也就是说子序列里既有左半的元素又有右半的元素而mid是左半最后一个元素、mid1是右半第一个元素所以跨中线必然同时包含mid和mid1。如果你只取左边一部分、不取右边那它本质上还是左半的子问题不应该在跨中情况里计算。理解了这一点跨中扫描代码的起点就顺理成章了左边从左往右扫出的最大和必须包含mid右边从mid1向右扫出的最大和必须包含mid1这样两者相加才能拼出一个跨越中点的连续序列。还有一个小陷阱如果左半部分是负数left_cross_max会是负数此时cross_max可能比只取右边还要小。但没关系因为我们在最终max()时会把纯右边的情况交给右半递归去处理跨中情况只是提供一个候选答案不要求它是全局最优。有些初学者会在跨中扫描时把left_sum和right_sum初始化为0这样遇到负数时左右贡献会被强制归0结果全负数数组返回0导致答案变成0而不是负数最大值。这就是我开头说的约定问题。如果你想避免这种问题就把初始值设为float(-inf)并且用累加后的当前值去更新如果你确认题目允许空子序列再初始化为0也不迟。4. 动态规划法一维状态如何拿下O(n)线性解4.1 状态定义与转移方程的直觉推导动态规划法解决这个问题的关键是定义清楚“状态”。设dp[i]表示以原数组第i个元素作为结尾的连续子序列的最大和。注意这个约束条件——“以第i个元素结尾”意味着这个子序列一定包含a[i]它是这个序列的最后一个元素。那么dp[i]怎么从dp[i-1]推导出来我们可以想一下以a[i]结尾的连续子序列要么是只包含它自己也就是从a[i]开始并以它结尾要么是把a[i]接到以a[i-1]结尾的某个最优子序列后面也就是“前一个最优尾巴加当前元素”。这两者取较大值就得到了状态转移方程dp[i] max(a[i], dp[i-1] a[i])这个方程看起来很简洁但它的思维量不小。你可以这样理解dp[i-1]既然是以a[i-1]结尾的最大和那如果这个和是正数接上a[i]显然比单独拿a[i]更强如果dp[i-1]是负数那“接上去”反而是拖累不如从a[i]重新开始一段新的子序列。所以这个max本质上是在做“续不续前缘”的决策。最终答案不是dp[n-1]而是所有dp[i]中的最大值。因为最大连续子序列不一定以最后一个元素结尾它在数组的任意位置都可能“封顶”。这一点我在初学时踩过坑以为求dp[n-1]就行结果全正数数组还行一旦最大值出现在中间位置答案就错了。4.2 动态规划标准实现与空间优化Kadane算法先写一份最直观的动态规划代码def max_subarray_dp(arr): n len(arr) if n 0: return 0 dp [0] * n dp[0] arr[0] max_sum dp[0] for i in range(1, n): dp[i] max(arr[i], dp[i - 1] arr[i]) max_sum max(max_sum, dp[i]) return max_sum这份代码时间复杂度O(n)空间复杂度O(n)因为用了一个长度为n的dp数组。但仔细观察你会发现dp[i]的计算只依赖dp[i-1]不需要更早的状态。那就没必要用一个数组存所有历史值只需要用两个变量滚动更新即可。这就是著名的Kadane算法也是面试官最期待的版本def max_subarray_kadane(arr): if not arr: return 0 current arr[0] # 以当前位置结尾的最大子序列和 best arr[0] # 全局最大子序列和 for i in range(1, len(arr)): current max(arr[i], current arr[i]) best max(best, current) return bestKadane算法的代码只有几行但它不是靠“背”就能真正掌握的。我教你一个检查自己是否理解的方法随便写一个数组手动模拟一遍每一轮current和best的变化。比如arr [-2, 11, -4, 13, -5, -2] i0: current-2, best-2 i1: currentmax(11, -211)11, best11 i2: currentmax(-4, 11-4)7, best11 i3: currentmax(13, 713)20, best20 i4: currentmax(-5, 20-5)15, best20 i5: currentmax(-2, 15-2)13, best20 答案21? 不答案是20对应区间[1,3]也就是11(-4)13手动模拟一遍之后你对这个算法的信任度会大幅提升面试时也能从容解释每一步背后的含义。4.3 动态规划为什么是最优解对比三种复杂度的本质差异动态规划之所以能把复杂度压到O(n)本质是因为它利用了子问题的重叠性。蛮力法枚举了太多重复区间。比如区间[1,3]的和在枚举[1,2]、[1,3]、[1,4]等区间时都被重复计算了很多遍分治法虽然避免了重复计算但它牺牲了一定的递归开销并且跨中扫描部分每次都要把整个区间扫一遍导致每层都要O(n)而动态规划通过“状态转移”的方式把问题分解成“当前元素接不接前面的尾巴”这个局部决策每个元素只参与一次状态更新全局最优解在递推过程中被自然维护下来。更直白地对比一下增长速度。假设n10万O(n^3)算法大约需要10^15次运算现代CPU每秒约10^9到10^10次运算理论上要跑好几天O(n^2)算法需要10^10次大约几秒到几十秒O(n log n)的分治法需要约10^6次运算毫秒级O(n)的Kadane算法只需要10^5次运算几乎瞬间完成。这个数量级差异是惊人的。也是通过这道题我第一次深刻理解了为什么算法设计课要花那么多时间讲“复杂度”这个概念。当你面对百万级数据时O(n^2)和O(n)已经不是“快一点”的区别而是“能跑”和“跑不动”的区别。5. 三种算法对比与边界测试实战5.1 复杂度与代码量对照表我把三种方法的核心指标整理成一张表方便你期末复习时对照算法时间复杂度空间复杂度思路核心代码量适用场景蛮力法三重循环O(n^3)O(1)枚举所有区间极少教学演示n500蛮力法两重循环O(n^2)O(1)固定起点扩展终点少小规模数据验证分治法O(n log n)O(log n)递归栈左/右/跨中三选一中等理解分治思想动态规划KadaneO(n)O(1)局部最优推导全局最优极少生产环境首选从工程角度Kadane算法几乎是完美答案。但从学习角度我建议你三种方法都亲手写一遍并且用同一组测试用例去验证。你会发现它们的结果完全一致这本身就是“殊途同归”的最好证明。5.2 边界测试用例集全负数、全正数、单元素与空数组在线判题系统最爱考的其实是边界情况而不是正常数据。我整理了一份必测的用例集你写完代码后一定要跑一遍测试用例输入期望输出易错点正常数据[-2, 11, -4, 13, -5, -2]20无全负数[-5, -3, -1, -7]-1不能返回0全正数[1, 2, 3, 4]10整个数组就是答案单元素[7]7递归终点与循环边界空数组[]取决于题目约定不做非法处理会崩溃最大值在尾部[1, -2, 3, 5]8不能用dp[n-1]直接当答案负数开头后反转[-1, 5, 100, -200, 300]305? 实际是5100-200300205? 等等验证current决策我实际操作中发现很多同学在全负数用例上翻车因为他们把dp数组初始化为0导致所有负数状态下dp[i]直接变成了0。而全正数用例上翻车的原因则是在动态规划里返回了dp[n-1]而不是整个dp数组的最大值。这两个坑几乎是期末考试和作业提交里的“经典送分题”。5.3 用随机数据对拍验证三种实现的一致性下面这个方法我强烈推荐给所有学算法的同学写一个“对拍器”用随机数生成大量测试数据同时跑三个版本的函数然后对比结果。这是我在做这道题时觉得最踏实的一步。import random def brute_force(arr): n len(arr) max_sum float(-inf) for i in range(n): s 0 for j in range(i, n): s arr[j] max_sum max(max_sum, s) return max_sum def divide_conquer(arr): def helper(l, r): if l r: return arr[l] m (l r) // 2 left_best helper(l, m) right_best helper(m 1, r) lsum 0 lmax float(-inf) for i in range(m, l - 1, -1): lsum arr[i] lmax max(lmax, lsum) rsum 0 rmax float(-inf) for j in range(m 1, r 1): rsum arr[j] rmax max(rmax, rsum) return max(left_best, right_best, lmax rmax) return helper(0, len(arr) - 1) def kadane(arr): cur arr[0] best arr[0] for i in range(1, len(arr)): cur max(arr[i], cur arr[i]) best max(best, cur) return best for _ in range(1000): n random.randint(1, 20) arr [random.randint(-100, 100) for _ in range(n)] a brute_force(arr) b divide_conquer(arr) c kadane(arr) if not (a b c): print(对拍失败:, arr, a, b, c) break else: print(1000组随机数据全部通过)跑完这个对拍脚本你就可以非常自信地说“我的三个算法实现都没有问题。”这个方法不仅适用于这道题任何你能写出一个慢但正确版本的算法题都可以用它来验证优化版本的正确性。我在刷题的时候几乎每道题都用这个套路能省下大量肉眼对比的时间。6. 常见问题排查与考试答题建议6.1 在线判题平台WA与TLE的常见原因分析在线判题平台上的提交结果最常见的就是WA错误答案和TLE超时。我结合自己当年踩过的坑总结出几个高频原因。WA的常见原因全负数数组没处理对返回了0而不是最大负数动态规划直接返回dp[n-1]而不是max(dp)分治法的跨中扫描边界写错比如漏了left端点或者越界访问数组长度为0时没有特殊处理直接访问arr[0]导致运行时错误结果超出int范围尤其是连续序列和很大的时候要用long long。TLE的常见原因就一个算法复杂度太高。如果你用O(n^2)甚至O(n^3)去处理n10^5级别的数据结局必然是超时。这时候你需要考虑切换到分治法或者动态规划法。我特别想强调一下“输出格式”这个不起眼的问题。很多题目要求输出最大值但也有些要求同时输出最大子序列的起止下标。如果题目要求输出“和”与“起止位置”你还得在Kadane算法里维护最佳区间的左右端点。我当年就因为在样例输出格式上多打了一个空格连续提交了三次WA最后发现是多余换行。6.2 一个案例分治法跨中扫描为何会出现负数最大值有位同学问过我一个问题当左半部分全是负数比如arr [-3, -5, -2, -4]分治法中跨中扫描的left_cross_max会是多少我们来看一下。假设mid 1从mid向左扩展left_sum依次为-5、-8left_cross_max初始化为负无穷更新后变成-5、-5所以left_cross_max -5。右半边从mid12开始扩展right_cross_max -2。因此cross_max -7。但整个数组的最大子序列是-2这在右半递归中会被正确找到。所以跨中扫描得到-7并不可怕因为我们最终取的是左半、右半、跨中三者的最大值而右半递归会给出正确答案。这里容易让初学者困惑的是为什么跨中扫描要处理负数如果左右全是负数跨中最大也是负数那直接初始化0不就好了答案是否定的。如果你把跨中扫描的累加初始化为0在全负数用例下你会得到cross_max 0而正确答案是负数最大值这就会导致WA。所以宁可让跨中结果为负数也不要强行初始化为0除非题目明确允许空子序列。6.3 期末机试与代码面试中的答题策略最后聊聊考试和面试。我自己的经验是遇到这种经典题答题节奏很重要。第一步先说清楚问题定义和边界条件“我假设序列非空全负数时返回最大值如果允许空子序列则返回0。”这一点在面试里很加分它说明你考虑问题严谨。第二步从最简单的蛮力法讲起说明枚举所有区间复杂度为O(n^2)或O(n^3)并指出可以优化。面试官不一定要求你写出最优解但一定希望看到你“有优化意识”。第三步给出动态规划思路重点解释状态定义dp[i]和转移方程dp[i] max(a[i], dp[i-1] a[i])。如果你能顺手讲出Kadane算法的空间优化版本这就是一个很完整的回答。第四步如果时间允许可以补充分治法并说明复杂度O(n log n)。这能展示你知识面的广度尤其是当面试官问“除了动态规划还有别的解法吗”的时候。我还想分享一个特别有用的笔试技巧如果题目允许使用辅助数组你可以先用“前缀和”的方式求区间和再结合双重循环枚举区间。这样做虽然还是O(n^2)但代码更简洁、不容易出错在某些数据规模限制不严的笔试环境里也够用。前缀和数组的定义是pre[i] a[0] a[1] ... a[i-1]那么区间[i, j)的和就是pre[j] - pre[i]写起来非常直观。6.4 全负数约定差异一道题引发的连锁思考关于“全负数时返回0还是返回最大负数”的问题我想再多说几句因为不同教材、不同在线评测平台、不同面试官的默认值真的不一样。LeetCode 53题的约定是“至少一个元素返回最大子数组和”全负数时返回最大的负数。而很多算法教材在讲“最大子段和”时默认允许空段因此全负数返回0。湘潭大学、头歌这类平台上的题目具体约定要看题面描述我见过有的明确说“结果可以为0”有的则没说。我的建议是上机做题前先用一个全负数的用例去试探题目的判定逻辑。如果你提交后WA再看一下是不是这个约定导致的。如果是面试手写代码就直接在代码注释里写上“这里采用XXX约定如果需要允许空子序列改成0即可”。这样既能体现你经验丰富又能避免和面试官产生理解偏差。这道题表面上只是一个“求最大和”的简单问题但它实际上牵扯出了“连续子数组到底怎么定义”“空数组怎么处理”“负数最大值怎么算”等一系列边界约定问题。能把这些问题想清楚比单纯背下一个Kadane算法要有价值得多。7. 实操总结与个人经验这道题我大概在算法课、机试准备、实习面试三个场景里加起来写过不下十遍每一次重新写都有新的收获。前几遍只是“会写”但讲不清楚为什么dp[i]要取max(arr[i], dp[i-1] arr[i])后来把三种算法都完整推导一遍才算真正建立起了“从暴力到最优”的思维链路。如果让我给一个学习路径上的建议我会说不要只背最优解一定要亲手把蛮力法、分治法、动态规划法三个版本都写出来并且跑同样的随机数据对拍。这个过程会逼你直面每种算法最容易出错的地方蛮力法的枚举边界、分治法的跨中扫描、动态规划的状态定义。等你把这三个版本的代码都吃透了以后遇到任何“子数组、子区间、最大值”类的问题你都能瞬间找到解题方向。最后再分享一个小技巧如果你在考场里突然忘了某个算法的实现细节优先写动态规划版本因为它代码量最少、状态转移最直观分治法虽然思路也很清晰但递归边界和跨中扫描的边界条件更容易写错。而蛮力法最好只在数据规模极小的题里用否则时间上会吃大亏。这道题的后半段其实就是在教你如何在“正确”和“高效”之间做取舍而这正是算法设计的真正魅力。