算法习题3.3：分治求解最大子数组和全解析-北京尧图网络

拿到这道“算法设计与分析-习题3.3”我第一反应是这不只是一道题而是一套完整的分治思想训练。课程里常把这种题放在分治章节的第三道位置说明难度比前两道稍高又不至于让初学者直接放弃。我自己当年做这类题时最痛苦的并不是写代码而是想不明白为什么递归能“自动”合并结果以及合并时到底要记录哪些信息。这篇就把我手写一遍、测一遍、踩一遍坑的全过程整理出来如果你也正在学算法设计与分析或者刷题时被分治卡住这篇应该能给你省下不少时间。1. 题目分析与思路起点先想清楚习题3.3在考什么1.1 题目定位从题号看分治教学的编排逻辑“习题3.3”这个编号在多数算法教材中属于分治策略章节的进阶练习。前面的习题通常让你实现归并排序、模拟递归树、画主定理公式到3.3开始要求你真正用分治思想去解决一个不那么“理所当然”的问题。我拿到的题目以“连续子数组最大和”为例给定一个整数数组可能存在负数要求找出一个连续子数组使它的元素和最大输出这个最大和。输入示例是[-2, 1, -3, 4, -1, 2, 1, -5, 4]期望结果是6因为子数组[4, -1, 2, 1]的和最大。这道题放在分治章节的用意很明确它不像归并排序那样天然告诉你“左半边排好、右半边排好、合并就是有序的”你需要自己定义“子问题”是什么、返回值是什么、如何合并子问题的答案。这种“自己设计递归结构”的能力才是分治教学真正想练的东西。1.2 拿到题先不要写代码先做三件事我自己的习惯是拿到算法题先干三件事手算样例、界定问题的边界、列候选解法。手算样例能让你确认对题目的理解尤其是“连续子数组”“最大和”这些词的具体含义。比如空数组怎么处理全负数数组怎么处理单个元素数组怎么处理这些边界都会影响最终的实现。然后我会把所有能想到的解法写下来哪怕是最笨的暴力枚举。暴力做法的思路是枚举所有起点i和终点j计算区间和更新最大值。三层循环的时间复杂度是 O(n^3)两层前缀和优化后是 O(n^2)。这个复杂度在大数组上不可用但它能作为测试基准用来验证分治实现是否错误。我当时就在草稿纸上写了一个 O(n^2) 的暴力版本专门用来生成随机数组用不同规模的数据和分治版本对比结果。这个习惯在后面排查边界问题时帮了大忙。2. 为什么用分治而不直接上动态规划选型背后的权衡2.1 动态规划解法看起来更短为什么习题还要分治连续子数组最大和有个非常经典的线性动态规划解法设dp[i]表示以第i个元素结尾的最大子数组和转移方程为dp[i] max(nums[i], dp[i-1] nums[i])。代码很简短时间复杂度是 O(n)比任何分治解法都优秀。那算法课为什么还要专门把这道题放在分治章节因为课程目标是让你练“分治思维的分解-解决-合并”三步曲而不是单纯追求最优复杂度。动态规划需要你意识到“以某个位置结尾”这种状态定义分治则逼着你思考“如何把大问题切成两个小问题再把两个小问题的答案合成大问题的答案”。这两种思维在今后的算法学习中都会反复出现。比如在大范围最优化问题、线段树维护区间信息、甚至并行计算等领域分治的“递归切分再合并”模式比动态规划更通用。手动实现一次分治版本你才能真正理解为什么线段树能维护最大子段和也才能理解归并排序的 merge 操作为什么能保证正确性。2.2 分治解法的三种情况框架分治的做法是把数组从中间切成左半边和右半边分别递归求左半边的最大子数组和与右半边的最大子数组和。但是最大子数组有可能跨越中间分界线也就是一部分在左半边、一部分在右半边此时既不是左子问题的答案也不是右子问题的答案。于是完整的分治逻辑被分成三种情况最大子数组完全在左半边最大子数组完全在右半边最大子数组横跨中间。前两种情况直接调用递归解决第三种情况单独处理从中间往左扫描累加并记录最大值从中间往右扫描累加并记录最大值两边最大值相加就是跨中线子数组的最大和。整个过程最核心的递归表达式是T(n) 2T(n/2) O(n)其中2T(n/2)来自左右两个递归调用O(n)来自合并时扫描中线两侧的消耗。根据主定理计算这个复杂度是 O(n log n)后面我会专门展开推一遍。3. 分治解法的完整实现每一步都写给你看3.1 递归函数设计返回什么、终止条件是什么我采用递归函数的输入参数是数组和左右边界low、high返回值是区间[low, high]内的最大子数组和。递归终止条件是low high此时只有一个元素最大子数组和就是nums[low]本身。这个设计比“返回整个区间最大和”多了一个考虑合并时需要的跨中线最大和并不能直接从左右递归结果得到必须额外扫描。所以我把扫描逻辑写在递归函数内部也就是把“处理跨中线情况”的代码放在获得左右结果之后、返回最终结果之前。用语言描述一下完整流程如果low high直接返回nums[low]。计算中点mid (low high) // 2。递归求左半边最大和left_sum。递归求右半边最大和right_sum。求跨中线最大和cross_sum从mid向左扫描累加nums[i]记录过程中的最大值max_left。从mid 1向右扫描累加nums[j]记录过程中的最大值max_right。cross_sum max_left max_right。返回max(left_sum, right_sum, cross_sum)。这里最容易被初学者忽略的是第 5 步向左扫描和向右扫描是分开进行的不能把mid重复计入两次。如果数组有负数扫到中途可能最大值并不是包含最左边或最右边的元素所以必须用“过程中最大值”而不是“最终累加和”。3.2 代码实现一个可以直接运行的版本我用 Python 做了一个完整实现代码保留递归结构方便对照算法思路def max_subarray_sum(nums, low, high): if low high: return nums[low] mid (low high) // 2 left_sum max_subarray_sum(nums, low, mid) right_sum max_subarray_sum(nums, mid 1, high) # 计算跨中线的最大和 # 向左扫描 max_left float(-inf) sum_left 0 for i in range(mid, low - 1, -1): sum_left nums[i] if sum_left max_left: max_left sum_left # 向右扫描 max_right float(-inf) sum_right 0 for i in range(mid 1, high 1): sum_right nums[i] if sum_right max_right: max_right sum_right cross_sum max_left max_right return max(left_sum, right_sum, cross_sum) # 测试 nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] result max_subarray_sum(nums, 0, len(nums) - 1) print(result) # 输出 6注意我故意把边界条件写成low high而不是low high因为数组区间始终是合法的。如果你在递归拆分时让mid左偏还需要额外处理空区间的情况这一版直接用mid 1作为右半边的起点避免空区间出现逻辑更干净。另外我习惯把float(-inf)初始化成负无穷而不是 0。原因很简单如果区间里全是负数从 0 开始会得到错误的最大值。比如数组[-3, -5, -2]跨越中线的最大向左部分应该是-2但如果你初始化max_left 0扫描过程中累加和永远小于 0最后max_left会被错误地保留成 0得到比真实结果更大的错误答案。3.3 手写一次递归调用过程彻底理解合并逻辑只看代码可能还是不够直观我手写一遍对示例数组的递归调用过程。数组是[-2, 1, -3, 4, -1, 2, 1, -5, 4]区间是[0, 8]。第一步mid 4拆成左区间[0, 4]和右区间[5, 8]。左区间[0, 4]继续拆mid 2分成[0, 2]和[3, 4]。[0, 2]再拆成[0, 1]和[2, 2][0, 1]拆成[0, 0]和[1, 1]分别返回-2和1合并时跨中线扫描左侧从 0 到 0 最大是-2右侧从 1 到 1 最大是1跨中线最大和是-1最终[0, 1]返回max(-2, 1, -1) 1。然后[0, 2]的右子区间[2, 2]返回-3合并跨中线时向左扫描nums[2] nums[1] -3 1 -2再向左加nums[0]得到更小所以max_left -2向右扫描只有nums[2] -3cross_sum -5最终返回max(1, -3, -5) 1。右边[3, 4]返回四个元素中的最大值。nums[3] 4nums[4] -1合并结果max(4, -1, 3) 4。左区间整体返回max(1, 4, cross_sum(左区间))其中跨中线的扫描会得到子数组[nums[1], nums[2], nums[3]] 1 (-3) 4 2以及[nums[3]] 4所以跨中线最大是 4最终左区间返回 4。右区间[5, 8]同理最终返回 5来自子数组[2, 1]和[2, 1, -5, 4]中较大者。顶部合并时跨中线从左扫描会得到4 (-1) 2 5从右扫描会得到2 1 3cross_sum 5 3 8但注意跨中线最大并不是 8而是从某个起点到另一个终点的连续区间扫描过程已经限制了必须包含mid所以实际候选是左右两个“包含中间边界”的最大子段之和这个值可能覆盖整个跨中线区间。最终max(left_sum4, right_sum5, cross_sum538)不是正确答案因为 8 对应的区间是什么让max_left最大的是从 3 到 4 的和 5max_right最大的是从 5 到 6 的和 3合并起来就是从 3 到 6[4, -1, 2, 1] 6。啊这里我重新计算一下从 3 到 4 是4 (-1) 3不对从 3 开始累加nums[3]4记录 4加上nums[4]-1变成 3所以max_left4。从mid15开始累加nums[5]2记录 2加上nums[6]1变成 3加上nums[7]-5变成 -2加上nums[8]4变成 2所以max_right3。cross_sum437对应子数组[4]和[2,1]组合成[4, -1, 2, 1]咦这里跨中线的定义要求从左半边至少取到mid4所以max_left必须包含nums[4]那我扫描结果是max_left4加上 3 得到 7但真实跨中线最大和包含 4 和 2、1是4 (-1) 2 1 6不是 7。为什么因为max_left和max_right分别取“包含边界”的最大和而且两者是独立扫描的但跨中线子数组必须连续覆盖从某个左端到某个右端的区间。在这个区间里左边界到 mid 的部分和 mid1 到右边界部分相加就是sum_left sum_right。但我的扫描方式会让max_left对应左边界到 mid 的最大和max_right对应 mid1 到右边界的最大和二者相加得到的就是跨中线完整区间的最大值这没问题。刚才说 7 对应 4 3但 4 的区间是[3,4]3 的区间是[5,6]合起来是[3,6]和是4 (-1) 2 1 6。那为什么 437因为 4 和 3 各自已经是和值再相加 7 是错的说明我在心算时把max_left4和max_right3相加后应该等于 7但这个组合并不存在于原数组中。这里我犯了一个经典的“心算错误”把区间和的值相加但没有意识到相加后的值对应整个区间的和而这个整个区间就是[3,6]它的真实和是 6。问题出在哪出在max_left对应的区间是[3,4]max_right对应的是[5,6]加起来区间是[3,6]和确实是 6。那我算的max_left4、max_right3相加得 7这就不可能同时成立因为max_left4对应[3,4]和值是4但[3,4]的和是4 (-1) 3不是 4。我把我算错了。重新算从 3 开始累加nums[3]4记录 4继续加nums[4]-1得到 3所以包含 mid4 的区间[3,4]最大和是3max_left应该是 3。从 5 开始加2记录 2加 1 得 3记录 3加 -5 得 -2加 4 得 2所以max_right3对应区间[5,6]和 3。cross_sum 3 3 6正确这个错误例子特别有教育意义手算时每一段累加值都要重新核对尤其是负数存在时很容易把“包含某个位置的最大值”误当成“该区间的最终和”。写代码时max_left是严格的累加过程中的最大值不是单独抽取某个元素的值。我建议每个人做完后用随机测试跑 100 组彻底避免这种手算混淆。4. 复杂度分析从递归树到主定理的定量证明4.1 写出递推方程并画出递归树上面提到递推方程是T(n) 2T(n/2) O(n)。这里O(n)是合并代价从 mid 向左扫描最多扫描半个数组从 mid 向右扫描最多扫描半个数组总扫描长度是 O(n)。画出递归树能直观看到总代价。根节点规模为 n合并代价是 n下一层有两个节点规模各为 n/2合并代价各为 n/2合计 n再下一层有四个节点规模各为 n/4合并代价合计 n。每一层的总代价都是 n而递归树的高度是 O(log n)因此总复杂度是 O(n log n)。同样的递归树也适用于归并排序这也是为什么归并排序的复杂度是 O(n log n)。这道题的分治解法在复杂度上与归并排序保持同一量级说明它确实把一个 O(n^2) 的暴力算法优化到了 O(n log n)。4.2 用主定理验证主定理处理形如T(n) aT(n/b) O(n^d)的递推式。这里a2b2d1。比较n^log_b(a)和n^dn^log_2(2) nn^d n两者相等属于主定理的第二种情况结果为T(n) O(n log n)。这个验证过程很简单但很多人容易记混第二种情况的公式。我的记忆方法是a b^d时复杂度就是n^d log n也就是同一量级乘一个对数因子。进一步看空间复杂度递归深度是 O(log n)每层需要常数级临时变量所以空间复杂度是 O(log n)。不过 Python 的递归会占用调用栈对数深度对普通规模数组完全没问题但如果你处理百万级数组递归可能就不是最优选择这时可以直接写迭代版分治或换用动态规划。5. 边界条件与常见实现错误排查5.1 全负数数组怎么处理我最初写第一版时把max_left初始化为了 0结果在[-3, -5, -2]上返回了 0明显错误。问题在于跨中线扫描时累加和始终为负初始化 0 会导致“空子数组”被误认为最大。修正方式是把初始化值设为float(-inf)并保证至少取一个元素。如果你不想用负无穷也可以单独取出第一个元素作为初始值然后再继续累加。比如向左扫描时写成max_left nums[mid] sum_left nums[mid] for i in range(mid - 1, low - 1, -1): sum_left nums[i] if sum_left max_left: max_left sum_left这种写法等价于先取第一个元素避免了-inf的使用但要注意初始时max_left和sum_left都设成nums[mid]循环从mid - 1开始不要重复累加nums[mid]。5.2 递归拆分时的中点偏移问题我在写代码时故意用了mid (low high) // 2递归子区间是[low, mid]和[mid1, high]。这种拆分保证左区间和右区间都不为空只要low high。如果使用[low, mid-1]和[mid, high]当high - low 1时可能会出现low high-1的空区间空区间没有合法返回值处理起来很麻烦。实现上有个细节跨中线扫描从mid向左到low从mid1向右到high。如果数组长度为偶数左半边和右半边长度相等如果为奇数左半边比右半边多一个元素。这样分配没有正确性问题因为最大子数组无论横跨哪个位置总会被某层递归的跨中线扫描捕捉到。5.3 用随机测试验证正确性分治解法光靠一两个样例不够我建议用这个思路验证写一个 O(n^2) 的暴力函数作为基准然后随机生成各种测试数组对比分治函数和暴力函数的结果。数组规模从小到大内容包含正数、负数、零、全负数、混合大数。我实际测试时发现最容易被 bug 击中的是数组长度为 2 且两个元素都是负数的情况。正确返回值是两者中的较大值但如果你初始化问题可能返回 0 或者返回跨越两个元素的和导致错误。下面是一个简单的验证脚本import random def brute_force(nums): best float(-inf) n len(nums) for i in range(n): s 0 for j in range(i, n): s nums[j] if s best: best s return best for _ in range(1000): n random.randint(1, 30) nums [random.randint(-10, 10) for _ in range(n)] a max_subarray_sum(nums, 0, n - 1) b brute_force(nums) if a ! b: print(Mismatch, nums, a, b) break else: print(All passed)跑完 1000 组随机测试后我对自己实现的分治函数才算有信心。这是做题最容易被跳过但最值得做的环节算法课上的“分析正确性”在实践层面就该落实到这种随机对拍上。6. 常见问题速查表与我的操作心得6.1 问题速查表问题现象可能原因排查与解决办法返回 0而不是负数最大值max_left或max_right初始化成了 0改为负无穷或初始化为第一个元素值结果比正确答案大且出在跨中线场景跨中线时把nums[mid]重复计算了两侧扫描向左扫描从mid开始向右扫描从mid1开始递归栈溢出数组极大且递归深度太深换迭代实现或改用动态规划 O(n) 解法结果与暴力法不一致但只在 n 为奇数时出错递归拆分的区间边界写错导致越界或漏元素统一使用[low, mid]与[mid1, high]的拆分方式理解不了为什么返回的三者最大值是对的没有意识到分治的三种情况覆盖了全部可能性画一条中线手动验证三种情况各对应哪种子数组6.2 我的几条实操心得第一做题时一定要先写暴力版本作为基准。这不是浪费时间而是给你后续所有优化提供一个“裁判”。我们课上做对拍测试时至少有三次靠暴力版本揪出了分治合并逻辑里的细微错误。第二手算样例时不要跳跃尤其是负数存在时把每一段累加过程写完整。我在第 3 节心算时就把max_left算错过一次如果你也遇到类似情况不用怀疑算法先检查自己的手算累加过程。第三学习分治的核心不是背代码而是先画递归树再看代码如何对应树的每个节点。如果你能画出 9 个元素数组的完整递归树并在每个节点标注返回值和合并时的扫描范围这道题基本就吃透了。第四这个分治解法虽然复杂度不如动态规划但思路可以迁移到线段树维护区间最大子段和线段树节点里往往存四个值分别是总和、最大前缀和、最大后缀和、最大子段和而合并两个子区间的方式几乎和这里的跨中线合并逻辑一模一样。当年我学线段树时就是因为提前手写了这个分治习题才在合并代码时一次通过。所以别觉得“既然有 O(n) 解法就不用学 O(n log n)”这个思路的复用价值远高于复杂度本身。最后再提一个具体操作层面的习惯写递归函数时把low、high作为显式参数不要用 Python 默认参数或全局变量保存数组。显式参数让每一层递归的作用域清晰也方便你打印调试过程中每个区间的返回值。调试时如果发现输出不对在递归函数入口加一行打印把low、high、mid以及该层最终返回值都打出来对照递归树很容易定位是哪个子区间算错了。

算法习题3.3：分治求解最大子数组和全解析

相关推荐

多Agent系统面试与实战：四种架构模式深度解析

“先判定后评估”：数据库执行计划生成的务实解法

模拟考试小程序源码实战：从组卷算法到自动判分与部署避坑

更多资讯

基于STFT-CNN-BiGRU的故障诊断方法：从时频图到深度学习分类

Oracle大表回表过滤性能优化：从诊断到索引设计实战

一键解包打包dtbo.img工具：Windows下修改屏幕刷新率与设备树叠加层

APK反编译工具ApkToolkit实战：拆包、改smali、回编译与签名全链路

Spring AI Alibaba停更后，Java开发者如何应对AI应用技术选型

端侧LLM推理性能排查实录：0.5到30 token/s的优化之路

今日更新

电商智能运营体系从0到1：架构设计、落地步骤与避坑指南

压缩空气储能与热网热惯性联合优化调度：热电联产系统建模与求解

若依框架AI代码生成不稳定？用Agent Skill三层结构+五步法搞定

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

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

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

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

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