1. 从一道“数学考试”题看动态规划的空间压缩技巧“数学考试”这个标题乍一看像是讲备考策略实际上它是一道经典的算法题出现在某在线编程平台的每日一题栏目中。题目的核心是给定一个长度为 n 的整数序列要求选出两个不重叠的、长度均为 k 的连续子区间使得这两个子区间的元素之和最大。输出这个最大的和。这道题表面上披着“数学”的外衣骨子里考的是前缀和与动态规划的配合以及如何在不超时的前提下处理大规模数据。我第一次遇到这道题的时候第一反应是暴力枚举两个区间的起点复杂度 O(n²)写完一提交直接超时。后来仔细想了想才发现这题有一个非常优雅的 O(n) 解法而且里面藏着几个容易踩的坑值得拿出来好好聊一聊。这道题适合谁呢如果你正在准备算法面试或者刚学完前缀和、动态规划想找一道有梯度的题目来练手那这道题非常合适。它不像有些难题那样需要复杂的图论或高级数据结构但也不是那种一眼就能看穿的简单题。它刚好卡在一个“需要动脑子但又不至于劝退”的位置上特别适合用来检验你对前缀和与动态规划的理解是否到位。接下来我会从题目分析、思路拆解、代码实现、边界处理、常见错误几个维度把这道题彻底讲透。2. 题目核心需求与暴力解法的局限性2.1 题目到底在问什么先把题目翻译成人话。你有一个数组比如[1, 3, 5, 7, 9, 2, 4, 6]再给你一个整数 k比如 k2。你要在这个数组里找两段连续的、长度为 k 的子数组这两段不能重叠也就是不能共用任何一个元素。然后你要让这两段子数组里所有元素的和加起来最大。最后输出这个最大的和。拿上面这个例子来说长度为 2 的子数组有哪些呢从下标 0 开始是[1,3]和为 4下标 1 开始是[3,5]和为 8下标 2 开始是[5,7]和为 12下标 3 开始是[7,9]和为 16下标 4 开始是[9,2]和为 11下标 5 开始是[2,4]和为 6下标 6 开始是[4,6]和为 10。现在要选两段不重叠的比如选下标 2 开始的[5,7]和下标 4 开始的[9,2]它们不重叠吗下标 2 和 3 是一段下标 4 和 5 是另一段确实不重叠和是 121123。还能不能更大选下标 3 开始的[7,9]和下标 5 开始的[2,4]和是 16622比 23 小。再试试下标 1 开始的[3,5]和下标 3 开始的[7,9]和是 81624这个更大。还有没有更大的下标 0 开始的[1,3]和下标 2 开始的[5,7]和是 41216。下标 1 开始的[3,5]和下标 4 开始的[9,2]和是 81119。看起来 24 是最大的。所以答案就是 24。2.2 暴力解法为什么不行最直观的想法就是枚举第一段的起点 i再枚举第二段的起点 j要求 j i k然后计算两段的和取最大值。计算两段和可以用前缀和优化到 O(1)但枚举 i 和 j 本身是 O(n²) 的。如果 n 是 10⁵ 级别n² 就是 10¹⁰肯定超时。如果 n 是 10⁶那就更不用想了。所以暴力枚举起点这条路走不通必须想办法把复杂度降下来。那能不能只枚举一个起点呢比如我只枚举第一段的起点 i然后想办法快速知道“在 ik 之后的所有位置中长度为 k 的子数组的最大和是多少”。如果能预处理出这个信息那枚举 i 就是 O(n)整体就是 O(n)。这个思路是可行的关键就在于怎么预处理。2.3 前缀和快速计算任意区间和在讲预处理之前先说一下前缀和这个基础工具。前缀和数组pre[i]表示原数组前 i 个元素的和即pre[i] a[0] a[1] ... a[i-1]pre[0] 0。有了前缀和任意区间[l, r]的和就是pre[r1] - pre[l]。对于长度为 k 的子数组如果起点是 i那么区间是[i, ik-1]和就是pre[ik] - pre[i]。前缀和的好处是一旦预处理出来查询任意区间和都是 O(1)。这道题里我们需要频繁计算长度为 k 的子数组的和所以前缀和是必不可少的。没有前缀和的话每次计算子数组和都要 O(k)整体复杂度会多一个 k 的因子很可能也会超时。3. 动态规划预处理从右往左的最大子数组和3.1 核心思路预处理后缀最大和刚才提到如果枚举第一段的起点 i就需要知道“从 ik 开始往后的所有长度为 k 的子数组中最大的和是多少”。我们可以定义一个数组maxSuffix[i]表示从下标 i 开始包括 i到数组末尾所有长度为 k 的子数组的最大和。注意这里的 i 是子数组的起点所以 i 的范围是 0 到 n-k。maxSuffix[i]怎么算呢可以从右往左递推。对于最右边的起点n-k它只有一个选择就是[n-k, n-1]所以maxSuffix[n-k] pre[n] - pre[n-k]。对于更左边的起点 i它可以选择以 i 为起点的子数组也可以选择以 i1 为起点的子数组也就是继承maxSuffix[i1]所以maxSuffix[i] max(pre[ik] - pre[i], maxSuffix[i1])。这样从右往左扫一遍就能把maxSuffix数组填好。有了maxSuffix之后再从左往右枚举第一段的起点 i第二段的最大和就是maxSuffix[ik]因为第二段必须在第一段之后且不重叠所以第二段起点至少是 ik。第一段的和是pre[ik] - pre[i]两者相加取所有 i 中的最大值就是答案。3.2 为什么从右往左而不是从左往右这里有一个细节值得说一下为什么maxSuffix要从右往左算而不是从左往右算一个maxPrefix其实两种方向都可以取决于你枚举的是第一段还是第二段。如果你枚举第一段就需要知道它右边所有子数组的最大和所以预处理后缀最大和从右往左算。如果你枚举第二段就需要知道它左边所有子数组的最大和那就预处理前缀最大和从左往右算。两种方式对称复杂度一样。我个人的习惯是枚举第一段预处理后缀最大和。因为这样在写代码的时候枚举 i 从左往右maxSuffix[ik]直接就能用逻辑比较顺。当然你也可以反过来没有本质区别。3.3 边界条件ik 不能越界枚举第一段起点 i 的时候i 的范围是 0 到 n-2k。为什么是 n-2k 而不是 n-k因为第一段占 k 个元素第二段也占 k 个元素两段不重叠所以总共至少需要 2k 个元素。第一段起点 i 最大只能是 n-2k这样第一段是[i, ik-1]第二段最早从ik开始最晚到n-1刚好占满剩下的 k 个元素。如果 i 再大第二段就不够 k 个元素了。所以枚举 i 的时候循环条件是i n - 2*k。这个边界很容易写错我第一次写的时候就写成了i n - k结果数组越界了。后来调试了半天才发现问题。所以这里一定要小心。4. 完整代码实现与逐行解析4.1 代码框架下面给出一个完整的 Python 实现我会逐行解释每一部分的作用。def solve(n, k, a): # 前缀和 pre [0] * (n 1) for i in range(n): pre[i1] pre[i] a[i] # maxSuffix[i] 表示从 i 开始到末尾长度为 k 的子数组的最大和 maxSuffix [0] * (n - k 1) maxSuffix[n-k] pre[n] - pre[n-k] for i in range(n-k-1, -1, -1): cur pre[ik] - pre[i] maxSuffix[i] max(cur, maxSuffix[i1]) # 枚举第一段起点 ans float(-inf) for i in range(0, n - 2*k 1): first pre[ik] - pre[i] second maxSuffix[ik] ans max(ans, first second) return ans4.2 前缀和数组的构建第一段代码构建前缀和数组。pre的长度是 n1pre[0]0pre[i1]pre[i]a[i]。这样pre[i]就表示前 i 个元素的和。比如a[1,3,5,7]那么pre[0,1,4,9,16]。要计算a[1]到a[2]的和就是pre[3]-pre[1]9-18也就是 358正确。这里注意 Python 的列表索引从 0 开始所以pre[ik] - pre[i]表示的是a[i]到a[ik-1]这 k 个元素的和。这个公式要记牢后面反复用到。4.3 maxSuffix 数组的递推maxSuffix的长度是n-k1因为长度为 k 的子数组的起点可以是 0 到 n-k一共 n-k1 个。最右边的起点是 n-k它对应的子数组是[n-k, n-1]和是pre[n]-pre[n-k]。然后从n-k-1往左遍历到 0每次计算当前起点的子数组和cur然后maxSuffix[i] max(cur, maxSuffix[i1])。这样maxSuffix[i]就表示从 i 到 n-k 这些起点中最大的子数组和。举个例子a[1,3,5,7,9,2,4,6]k2n8。pre[0,1,4,9,16,25,27,31,37]。maxSuffix长度是 7下标 0 到 6。maxSuffix[6] pre[8]-pre[6] 37-27 10对应子数组[4,6]。maxSuffix[5] max(pre[7]-pre[5], maxSuffix[6]) max(31-25, 10) max(6, 10) 10。maxSuffix[4] max(pre[6]-pre[4], maxSuffix[5]) max(27-16, 10) max(11, 10) 11。maxSuffix[3] max(pre[5]-pre[3], maxSuffix[4]) max(25-9, 11) max(16, 11) 16。maxSuffix[2] max(pre[4]-pre[2], maxSuffix[3]) max(16-4, 16) max(12, 16) 16。maxSuffix[1] max(pre[3]-pre[1], maxSuffix[2]) max(9-1, 16) max(8, 16) 16。maxSuffix[0] max(pre[2]-pre[0], maxSuffix[1]) max(4-0, 16) max(4, 16) 16。所以maxSuffix [16, 16, 16, 16, 11, 10, 10]。这个结果对不对呢从下标 0 开始的所有长度为 2 的子数组最大和是 16下标 3 开始的[7,9]所以maxSuffix[0]16正确。从下标 3 开始的最大和也是 16正确。从下标 4 开始的最大和是 11下标 4 开始的[9,2]正确。从下标 5 开始的最大和是 10下标 6 开始的[4,6]正确。4.4 枚举第一段并计算结果最后枚举第一段起点 i范围是 0 到 n-2k。对于每个 i第一段和是pre[ik]-pre[i]第二段最大和是maxSuffix[ik]两者相加更新答案。注意ik是第二段的最早起点maxSuffix[ik]表示从ik开始到末尾的最大子数组和正好保证了两段不重叠。继续上面的例子n8k2n-2k4所以 i 从 0 到 4。i0 时第一段和pre[2]-pre[0]4第二段最大和maxSuffix[2]16总和 20。i1 时第一段和pre[3]-pre[1]8第二段最大和maxSuffix[3]16总和 24。i2 时第一段和pre[4]-pre[2]12第二段最大和maxSuffix[4]11总和 23。i3 时第一段和pre[5]-pre[3]16第二段最大和maxSuffix[5]10总和 26。i4 时第一段和pre[6]-pre[4]11第二段最大和maxSuffix[6]10总和 21。最大值是 26对应 i3第一段是[7,9]第二段是[4,6]和是 161026。等等之前我手算的时候说最大是 24现在怎么变成 26 了让我重新检查一下。原数组是[1,3,5,7,9,2,4,6]k2。i3 时第一段是下标 3 和 4也就是[7,9]和是 16。第二段从下标 5 开始maxSuffix[5]是 10对应下标 6 开始的[4,6]和是 10。两段是[7,9]和[4,6]它们不重叠吗第一段占下标 3 和 4第二段占下标 6 和 7中间下标 5 是2没有被用到所以确实不重叠。和是 26。那我之前手算的时候为什么说最大是 24因为我漏掉了这个组合。所以正确答案应该是 26。这说明手算容易出错还是得靠代码。5. 常见错误与调试技巧5.1 数组越界maxSuffix 的长度和索引第一个常见的错误是maxSuffix数组的长度和索引搞错。maxSuffix的长度应该是n-k1因为起点从 0 到 n-k。如果你写成n-k那最后一个起点 n-k 就没有位置放了会越界。另外在递推的时候maxSuffix[n-k]是初始值然后从n-k-1往左遍历。如果你从n-k开始往左那maxSuffix[n-k]会被重复计算虽然结果可能一样但逻辑上不清晰。还有一个容易错的地方是枚举第一段起点时循环的上界。应该是n-2k不是n-k。如果你写成n-k那么当 i 接近 n-k 时ik会超过n-k访问maxSuffix[ik]就会越界。这个错误我在第一次写的时候犯了调试的时候看到IndexError才反应过来。5.2 前缀和计算子数组和的公式前缀和计算子数组和的公式是pre[ik] - pre[i]不是pre[ik-1] - pre[i-1]。虽然这两个在数学上等价但用前者更不容易出错因为pre的长度是 n1pre[ik]当ikn时是合法的而pre[ik-1]当ik-1n-1时也是合法的但如果你不小心写成pre[ik] - pre[i-1]当 i0 时pre[-1]在 Python 里会取到最后一个元素导致错误。所以统一用pre[ik] - pre[i]最安全。5.3 答案初始化为负无穷答案ans要初始化为负无穷因为数组里可能有负数子数组和可能是负的。如果你初始化为 0当所有子数组和都是负数时你会得到 0但正确答案应该是某个负数。所以用float(-inf)或者一个足够小的数比如-10**18。5.4 数据范围与整数溢出如果题目给的数组元素和 n 都很大比如 n 是 10⁵元素是 10⁹那么子数组和可能达到 10¹⁴在 Python 里整数没有溢出问题但在 C 或 Java 里就要用long long。这一点在跨语言实现的时候要注意。Python 的好处就是不用操心溢出但速度可能慢一些如果 n 特别大可能需要优化输入输出。6. 复杂度分析与优化空间6.1 时间复杂度和空间复杂度这个算法的时间复杂度是 O(n)因为前缀和构建是 O(n)maxSuffix递推是 O(n)枚举第一段也是 O(n)总共三次线性扫描。空间复杂度是 O(n)因为用了pre和maxSuffix两个数组长度都是 O(n)。对于 n10⁵ 或 10⁶ 来说这个复杂度完全可以接受。能不能把空间优化到 O(1)理论上可以因为maxSuffix在枚举第一段的时候是从左往右用的而它是从右往左算的所以不能边算边用。但你可以把maxSuffix存下来或者换一种思路从左往右算一个maxPrefix然后从右往左枚举第二段这样maxPrefix可以边算边用但maxPrefix本身还是需要 O(n) 的空间除非你只用一个变量滚动更新。不过这道题空间 O(n) 已经足够了没必要过度优化。6.2 如果 k 很大怎么办如果 k 很大比如 k 接近 n/2那么 n-2k 可能很小甚至为负数。如果 n 2k那就无法选出两段不重叠的长度为 k 的子数组这时候应该返回什么题目一般会保证 n 2k但如果没有保证你需要处理这种情况。可以返回 0 或者一个特殊值具体看题目要求。我在实际做题的时候遇到过 n 2k 的测试用例当时没处理结果数组越界了。后来加了一个判断if n 2*k: return 0才通过。6.3 如果要求输出具体方案而不只是最大值有时候题目会变种要求输出这两段子数组的起点或者输出这两段子数组本身。这时候你需要在更新答案的时候记录下 i 和maxSuffix对应的起点。maxSuffix只记录了最大值没有记录取得最大值的起点所以你需要额外维护一个数组argSuffix来记录起点。或者在枚举第一段的时候对于每个 i你还需要知道maxSuffix[ik]对应的起点是哪个。这可以通过在递推maxSuffix的时候同时记录argSuffix来实现。这个变种稍微复杂一点但思路是一样的。7. 个人实操心得与避坑清单7.1 手算容易漏情况一定要写代码验证我在前面手算的时候漏掉了[7,9]和[4,6]这个组合导致算出来的最大值是 24 而不是 26。这说明手算很容易出错尤其是当数组元素比较多的时候。所以我的习惯是先手算一个小例子来验证思路然后写代码用代码跑这个小例子看看结果和手算是否一致。如果不一致先检查代码如果代码逻辑没问题那可能是手算错了。这个过程能帮你快速定位问题。7.2 边界条件要单独测试这道题的边界条件主要有几个n 刚好等于 2k这时候只有一种选法就是第一段占前 k 个第二段占后 k 个数组里有负数k1 的情况n 很大的情况。我建议你写完之后针对这几个边界条件分别造一个测试用例手动跑一遍看看结果对不对。比如 n4k2数组是[1,2,3,4]那么唯一的选择是第一段[1,2]和第二段[3,4]和是 3710。你可以用代码跑一下看看输出是不是 10。7.3 用打印调试法定位问题如果你写的代码结果不对但又不知道哪里错了可以在关键位置加打印语句。比如打印pre数组看看前缀和算得对不对打印maxSuffix数组看看递推对不对打印每次枚举的first、second和ans看看哪一步出了问题。这个方法虽然原始但非常有效。我调试这道题的时候就是靠打印maxSuffix发现自己的递推方向写反了。7.4 常见问题速查表问题现象可能原因解决方法数组越界 IndexErrormaxSuffix 长度不对或枚举上界写成 n-k检查 maxSuffix 长度为 n-k1枚举上界为 n-2k答案偏小漏掉了某些组合或者 maxSuffix 递推方向错了检查 maxSuffix 是否从右往左算是否取了 max答案偏大两段重叠了检查第二段起点是否至少为 ik负数用例结果错误ans 初始化为 0改为 float(-inf) 或足够小的负数超时用了 O(n²) 暴力改用前缀和 maxSuffix 的 O(n) 解法7.5 一个容易忽略的细节maxSuffix 的语义maxSuffix[i]表示的是从 i 开始到末尾所有长度为 k 的子数组的最大和。注意这里的 i 是子数组的起点不是元素下标。有些人在实现的时候会把maxSuffix[i]理解成“从元素 i 开始往后的最大和”然后计算的时候用pre[jk]-pre[j]其中 j i这样也能得到正确结果但语义上容易混淆。我建议在变量命名和注释里写清楚避免自己把自己绕进去。8. 从这道题延伸出的通用解题模板8.1 “两段不重叠子数组”问题的通用思路这道题其实是一个模板题很多类似的题目都可以用同样的思路解决。比如“选两个不重叠的子数组使得它们的和最大”或者“选两个不重叠的子数组使得它们的差的绝对值最小”。核心思路都是枚举分割点预处理左边的最优值和右边的最优值然后合并。对于这道题分割点就是第一段的结束位置左边是固定长度的子数组右边也是固定长度的子数组。如果是变长的话预处理的方式会稍微不同但框架是一样的。具体来说你可以定义一个leftMax[i]表示从 0 到 i 范围内某个子数组的最优值rightMax[i]表示从 i 到 n-1 范围内某个子数组的最优值。然后枚举分割点合并leftMax[i]和rightMax[i1]。这道题里因为子数组长度固定为 k所以leftMax和rightMax的递推比较简单。如果长度不固定可能需要用动态规划来求最大子数组和那就是另一个经典问题了。8.2 前缀和与动态规划的结合技巧前缀和和动态规划经常一起出现。前缀和用来 O(1) 计算区间和动态规划用来预处理最优值。这道题里maxSuffix的递推就是一个简单的动态规划maxSuffix[i] max(当前起点的子数组和, maxSuffix[i1])。这个递推方程很直观但写的时候要注意方向。类似的题目还有“最大子数组和”的 Kadane 算法也是动态规划的思想但不需要前缀和。所以具体问题具体分析不要生搬硬套。8.3 如何判断一道题是否适合用这种解法一般来说如果题目要求“选两个不重叠的区间”或者“选一个区间使得某个指标最大”并且区间的长度是固定的或者可以用前缀和快速计算那么就可以考虑用“枚举分割点 预处理左右最优值”的方法。如果区间长度不固定但可以用动态规划求最优值也可以套用这个框架。关键是要能快速计算“左边的最优值”和“右边的最优值”并且合并的代价是 O(1)。如果合并的代价不是 O(1)那可能需要更复杂的数据结构比如线段树或树状数组。9. 不同语言实现的注意事项9.1 Python 实现的性能优化Python 的代码写起来简洁但速度可能是个问题。如果 n 是 10⁶O(n) 的算法在 Python 里可能也要跑一两秒。这时候可以用一些优化技巧比如用sys.stdin.read快速读入用列表推导式代替循环用局部变量代替全局变量。另外maxSuffix数组可以用array模块或者list来存list在 Python 里已经很快了。如果还是超时可以考虑用 PyPy 提交或者换 C 写。9.2 C 实现的溢出问题C 里要注意整数溢出。如果数组元素是 10⁹n 是 10⁵那么子数组和可能达到 10¹⁴int存不下必须用long long。前缀和数组和maxSuffix数组都要用long long。另外ans初始化为LLONG_MIN或者-1e18。输入输出用scanf和printf比cin和cout快如果数据量大的话。9.3 Java 实现的数组初始化Java 里数组默认初始化为 0但maxSuffix的最后一个元素需要手动赋值。另外Java 的long是 64 位的可以存下 10¹⁴。ans初始化为Long.MIN_VALUE。Java 的输入输出用BufferedReader和StringTokenizer比较快Scanner可能超时。10. 这道题背后的算法思想总结这道题虽然披着“数学考试”的外衣但本质上是一道动态规划 前缀和的题目。它的核心思想是“枚举分割点预处理左右最优值”这个思想在很多算法题里都有体现。比如“买卖股票的最佳时机”系列也是枚举分割点预处理左边的最小值和右边的最大值。再比如“最大子数组和”的变种也是类似的思路。所以掌握这道题不仅仅是学会了一道题而是掌握了一类题的解法。另外这道题也提醒我们暴力解法虽然简单但往往不是最优的。在面试或者比赛中看到 O(n²) 的解法要下意识地想想能不能优化到 O(n) 或 O(n log n)。优化的方向通常是用空间换时间预处理一些信息避免重复计算。这道题里maxSuffix就是预处理出来的信息避免了每次枚举第二段时重新扫描。最后这道题的边界条件比较多容易出错。写代码的时候要细心多测试几个用例尤其是边界用例。我个人的经验是写完代码后至少造三个测试用例一个普通的一个全是负数的一个 n2k 的。如果这三个都能过那基本就没问题了。踩过几次坑之后我发现算法题最怕的就是“想当然”。你以为边界条件不会出现结果测试用例里就有你以为手算的结果是对的结果代码跑出来不一样。所以多写多练多调试才是提高算法能力的正道。这道“数学考试”题我前前后后做了三遍第一遍超时第二遍越界第三遍才通过。每一次失败都让我对前缀和和动态规划的理解更深了一层。希望你做这道题的时候也能从中收获一些东西。