Maximum Subarray Sum IICSES P1644这道题我第一次看到时直接把它当成了Kadane算法的换皮题最大连续区间和嘛经典到不能再经典。可真正动笔推演才发现题目多出来的那个长度区间约束直接把问题从一维线性DP升级成了“前缀和单调队列”的经典组合。如果你正在刷CSES的题库或者准备算法面试前集中补滑动窗口和单调队列这道题值得细读。我在这篇文章里把思路变形、队列维护的边界、两版实现和几次WA的调试过程完整走一遍帮你一次吃透。1. 先看清题最大连续区间和为何加了“长度上下限”就变难1.1 从Kadane到约束问题的第一反应原版最大连续子数组和是一个经典问题。给定一个长度为n的整数数组要求找连续的一段使和最大。Kadane算法从上世纪八十年代沿用到今天代码只有几行核心思想是贪心以i结尾的最大子数组和要么单独从当前元素开始要么接在前一个结尾的最优后缀后面。之所以可以直接取这两种情况的较大值是因为一个负数前缀对后续来说完全没有价值丢掉它之后不会错过任何更优解。CSES P1644把题目改成了Maximum Subarray Sum II多了两个输入参数a和b要求子数组长度必须在[a, b]之间。第一次看到这个改动时我内心是有点轻敌的因为“滑动窗口双指针”看起来很熟。但真正一推导就发现长度下界的加入直接打破了Kadane的贪心结构即使某一段前缀和为负只要它被强制包含在长度内我们就不能丢弃它。更麻烦的是长度还有上界意味着我们不能贪心地一直延伸最优窗口必须在一个有限范围内做选择。连续两个约束等于把“全局最优”压缩成“约束最优”问题的复杂度立刻不一样了。这里有个很直观的反例数组是[10, -100, 99]a2b3。Kadane会选出99但长度只有1不满足最小长度2。再看合法区间长度为2的有-90和-1长度为3的只有整个数组9所以正确答案是9。为了让长度达标我们必须被迫包含-100这个很负的段Kadane那种“看到负累计就丢弃”的策略完全失效。1.2 暴力枚举与数据规模的不可调和最朴素的枚举思路是枚举所有l和r检查长度r-l是否落在[a, b]内再计算和。如果先用前缀和预处理单次区间和查询是O(1)但枚举对数仍然是O(n^2)。CSES输入规模n最大为2×10^5O(n^2)意味着大约4×10^10次操作即使每秒跑10^9次也远远不够。还要注意一个隐蔽的坑题目元素绝对值可到10^9这意味着前缀和跨度能到2×10^14。这个量级用32位整数存储一定会溢出代码里如果不加小心很容易在不知不觉间得到一个错误答案。后面调试部分还会专门说这个问题。顺着这条思路我们必须把复杂度压到O(n log n)或O(n)。面对“区间长度限制极值查询”这类问题常规武器库里有线段树、树状数组、堆和单调队列。为什么最终选择单调队列后面会有详细对比。1.3 固定右端点把问题改成候选区间的查询既然无法同时优化两端那就固定一端。我们枚举右端点r每次只考虑以r结尾的子数组。对于固定的r合法的左端点l前缀和下标需要同时满足r - l a和r - l b整理一下就是l ∈ [r-b, r-a]。区间和表示为pre[r] - pre[l]当r固定时pre[r]是常量想让区间和最大等价于在窗口[r-b, r-a]里找到l使得pre[l]最小。到这里问题已经变成一个标准的“滑动窗口最小值”查询随着r从a逐步增加到n窗口右边界r-a不断增加左边界r-b也不断向右推每次窗口右端新进一个下标左侧可能挤掉一个下标。这个转化是整个题目的灵魂。很多人看到这题第一反应是维护“滑动窗口和”那是被固定长度窗口题带偏了。正确思路是维护“滑动窗口内候选前缀和的最小值”前缀和数组一旦计算好后续操作完全不碰原数组元素两个下标之差就是完整区间和既干净又不容易出错。2. 前缀和把“区间求和”降维成“两点求差”2.1 前缀和的定义与边界处理设pre[0] 0pre[i] sum(arr[1..i])其中i从1到n。为什么要留一个pre[0]因为子数组[l1, r]的和正好等于pre[r] - pre[l]当l0时代表从第一个元素开始取这时pre[0]0是必不可少的哨兵。数组下标从1开始读入会避免很多边界混乱我习惯声明长度为n1的vectorpre[0]固定为0。在读入数据时可以直接构造前缀和不需要额外存原数组for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; }这一步之后原数组就不需要保留了所有操作都在pre上做。2.2 为什么前缀和方案比直接维护窗口和更稳如果直接在滑动窗口里存元素由于窗口长度可变从a到b删除左侧时你得记录窗口内数值总和新加右侧也得加值。这样做虽然也能算对但逻辑上容易混淆窗口长度变化的边界、删除的是哪个元素、是否删除合法元素。前缀和方案完全绕开了这些细节窗口维护的不是“窗口内的和”而是“窗口内候选l对应的pre[l]值”。窗口移动被抽象成下标区间的滑动数值上是单调队列在维护pre值的大小关系操作非常规整。这也解释了为什么这类题的标准解几乎都是“前缀和单调队列”而不是那种“动态窗口和”的做法。2.3 从例子里看前缀和的威力沿用上面的例子arr [1, -3, 1, 5, -2, 3]pre数组为[0, 1, -2, -1, 4, 2, 5]。想找r4、长度2到4的子数组只需看窗口[0, 2]内的pre值。最小是pre[2]-2于是得到最优区间和pre[4]-pre[2]6。手算验证arr[3]arr[4]156长度是2合法。整个过程只用比较几个pre没有做任何元素累加这就是前缀和的优势把区间求和从“重复累加”变成“一次减法”。3. 单调队列滑动窗口最小值问题的标准解法3.1 窗口内最小值的三种候选方案窗口左边界、右边界都随r线性移动我们每秒要回答“当前窗口内pre最小值是谁”。最暴力的做法是每次扫描窗口复杂度O(n×窗口大小)。用优先队列堆也可以每轮压入新下标按pre排序但堆不支持快速删除任意过期元素只能懒删除——每次取堆顶时检查下标是否过期过期就丢弃。这个方案复杂度O(n log n)能过题但代码要处理惰性删除写起来没有单调队列清爽且常数偏大。用线段树则是把pre数组建树区间查询最小值一套模板下来最少五六十行对这道题有点杀鸡用牛刀。单调队列的优势在于窗口是单调滑动的每个下标只会进出队列一次整体摊还O(n)队列内维护一个“由小到大”的候选序列取最小值直接看队头O(1)。它正是为“滑动窗口最值”量身定做。3.2 入队与出队的两个原则队列里存的是pre数组的下标而不是pre的值。为什么存下标因为判断过期需要看下标是否滑出区间同时比较值大小还得通过下标访问pre。我总结成两个原则原则一维持队列内pre值单调递增。新下标入队前把所有pre值大于等于pre[新下标]的队尾弹出。因为队列内值相同的新下标寿命更长旧下标留着没有任何优势。原则二每次取队头前先把所有下标小于窗口左边界的队头弹出。漏掉第一点队内不是单调的取的未必是最小漏掉第二点队头可能已过期答案会被历史值污染。两个原则缺一不可。排序上我习惯顺序是“入队维护单调性” - “弹出过期队头” - “计算答案”。先入队再弹出是安全的因为新入队的下标是当前窗口内最靠右的候选必然不会在弹出过期元素时被误删。3.3 手工模拟一次完整过程接着用arr [1, -3, 1, 5, -2, 3]a2b4来走流程。pre为[0, 1, -2, -1, 4, 2, 5]。r2窗口[2-4, 2-2][-2, 0]实际下标只取0。入队下标0pre[0]0队列变为[0]。队头0合法anspre[2]-pre[0]-2。r3窗口[-1, 1]实际下标0到1。入队下标1pre[1]1队尾pre[0]0小于1不弹出队列为[0, 1]。队头0合法ansmax(-2, pre[3]-pre[0])-1。r4窗口[0, 2]。入队下标2pre[2]-2它比队尾pre[1]1小且比pre[0]0也小于是连续弹出0和1队列变为[2]。队头2合法ansmax(-1, 4-(-2))6。r5窗口[1, 3]。入队下标3pre[3]-1队尾pre[2]-2更小不弹出队列为[2, 3]。队头2合法因为2 5-41ansmax(6, 2-(-2))4。r6窗口[2, 4]。入队下标4pre[4]4队尾pre[3]-1更小不弹出队列为[2, 3, 4]。队头2合法ansmax(4, 5-(-2))7。最终输出7对应子数组arr[3..6]即15-23长度4在[2,4]内。这个例子中窗口右边界到了4之后没有出现队头过期的情况所以看起来“没有弹旧”。要验证弹旧把b改小一些比如b3r6时窗口变成[3,3]下标2就过期了答案会变成pre[6]-pre[3]6。这个退化用例我建议你亲手推一遍对理解边界很有帮助。4. 两版工程实现与关键代码剖析4.1 C实现与逐行注释下面是一份我认为最简的C实现。代码不长但每一行都有讲究。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, a, b; cin n a b; vectorlong long pre(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; } dequeint dq; long long ans LLONG_MIN; for (int r a; r n; r) { int cand r - a; while (!dq.empty() pre[dq.back()] pre[cand]) { dq.pop_back(); } dq.push_back(cand); while (!dq.empty() dq.front() r - b) { dq.pop_front(); } ans max(ans, pre[r] - pre[dq.front()]); } cout ans \n; return 0; }逐行说明pre用long long。n最大2×10^5且每个元素绝对值可达10^9前缀和跨度能到2×10^14int一定爆。循环从ra开始。r小于a时不存在任何合法子数组直接跳过。每轮新加入的候选左端点是cand r-a它对应长度恰好为a的子数组。窗口的右边界就是r-a所以这个下标刚好是窗口内最靠右的候选。弹出队尾时用而不是保证pre相同时留下更靠右的下标。靠右的下标寿命更长对后续r更有利。弹出队头时判断front() r-b。注意等号不能写front()等于r-b时子数组长度正好是b依然合法。最后ans max(ans, pre[r] - pre[dq.front()])。4.2 Python实现与性能提醒如果比赛环境允许Python可以直接翻译。Python的collections.deque用起来甚至更简洁import sys from collections import deque def solve(): input sys.stdin.readline n, a, b map(int, input().split()) arr list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] arr[i - 1] q deque() ans -10**30 for r in range(a, n 1): cand r - a while q and pre[q[-1]] pre[cand]: q.pop() q.append(cand) while q and q[0] r - b: q.popleft() ans max(ans, pre[r] - pre[q[0]]) print(ans) solve()跑CSES的2×10^5数据用PyPy通常没问题注意用sys.stdin.readline加速输入。如果遇到时间限制很紧可以尝试把pre的构建改成生成器表达式但实测readline这种写法已经足够稳定。4.3 复杂度与方案取舍这里把三种可行方案放在一张表里方便你根据场景选择方案时间复杂度代码量备注暴力扫描O(n×窗口长度)最短只能处理小数据线段树/树状数组O(n log n)长思路通用但实现重堆懒删除O(n log n)中要处理过期堆顶容易漏单调队列O(n)很短本题最优解这道题在CSES的位置很妙它前面已经有普通版Maximum Subarray Sum后面接着就需要你掌握前缀后缀的各种变体。如果只会线段树虽然也能过但会错失单调队列这个重要的窗口工具。我个人的建议是第一次做可以试着用线段树过一遍搞清楚建模过程然后必须用单调队列重写一遍体会O(n)的优雅。5. 实战中的五个高频错误与调试方法5.1 错误一把ans初始化为0这是我第一次提交WA后发现的低级错误。题目要求子数组长度至少aa1不允许选空区间。假设数组是[-5,-2,-3]a2b3合法的子数组和全是负数[-5,-2]-7[-2,-3]-5整个数组-10正确答案是-5。如果ans初始化为0max函数会永远保留0输出错误答案。正确做法是初始化成LLONG_MIN或Python里的-10**30。5.2 错误二入队时机错一位有的同学写的时候循环里先push_back(pre[r])再计算这样计算以r为右端点时会错误地把lr当作左端点相当于允许长度为0的区间。这种写法在有些允许空区间的变体题里没问题但P1644不允许。正确的时机是加入cand r-a这个下标保证每轮右端r对应的最小合法左端点刚进窗口一步不多。5.3 错误三队头过期漏清或清过头如果弹出条件写成dq.front() r-b会把长度正好等于b的合法方案丢掉如果写成dq.front() r-b-1之类又把本该保留的下标弹走了。建议在更新ans之前先清过期队头顺序固定成“入队维护单调性 - 弹出过期队头 - 计算答案”这样最不容易错。5.4 错误四int溢出我见过有人在CSES上把pre数组声明成int本地样例过了大数据直接WA。CSES的反馈是WA不是RE因为溢出后只是数值错程序不会崩溃排查起来更隐蔽。养成习惯凡是前缀和、区间和的计算一律先开long long。尤其在C里short和int混用很容易在不知不觉中发生隐式转换丢精度。5.5 测试用例构造与退化验证刷题最怕“样例过了就交”。这道题我建议自己构造三类用例全正数比如[1,2,3,4]a1b4。这时最优是全部加起来等于10既能验证窗口上界处理正确也能验证单调队列里的弹旧逻辑不会误伤。全负数比如[-5,-2,-3]a2b3。验证ans不是初始化为0。负正交替比如[5,-100,200,-50,10]a2b3。这个例子手算答案不唯一但可以用来对比程序输出。我实际调试时最常用的是退化测试把a和b设成相等比如ab2问题退化成固定长度2的滑动窗口。此时单调队列应该输出与“固定窗口双指针”一致的结果。用这个退化用例几乎能立刻看出入队时机和过期条件是否写反。再补充一个速查表症状可能原因排查方式样例过大数据WApre用int溢出全部改成long long全负数组输出0ans初始化为0改用LLONG_MIN输出偏大队头过期没弹出检查弹出条件是否为front() r-b输出偏小入队时机错位检查入队下标是否为r-aab2时结果不对窗口边界理解错手推固定窗口双指针对照6. 从这道题延伸出去的几个想法6.1 如果题目改成求最小连续区间和思路完全对称窗口内要找最大前缀和队列维护单调递减队头最大其余不变。初次尝试时我把while的错写成然后取min结果样例都过不了。因为这个看起来“对称”的操作实际没那么容易直接套建议对称做法也要重新推一遍边界再写。6.2 如果长度下限是0那空子数组也合法有趣的是Kadane可以回归或者单调队列里也可以提前把pre[0]0放在窗口里。但绝大多数竞赛题里a是正整数记住这个边界差别即可。这个问题也是面试中常见的追问面试官给你这道题第二个问题往往就是“如果允许空区间你的代码要怎么改”。6.3 解题套路的识别信号“给定长度范围求区间最值/和最大”这一类问题只要数据范围到2×10^5基本都能套前缀和单调队列。识别信号很明确题目同时出现区间长度限制[a, b]和极值需求。问题可以转化成“每个右端点找一个左端点”。左端点范围随右端点单调滑动。看到这三个信号直接考虑前缀和单调队列。做题多了你会发现单调队列很少单独出现它经常和前缀和、DP状态优化绑定在一起。比如有些滑动窗口优化DP的题本质上就是在转移方程里维护一个窗口内最值和本题的处理手法如出一辙。我个人在实际刷题中最大的体会是代码本身并不难难的是第一次想通“为什么r-a这个下标会在r循环中恰好作为新的入队候选”。我反复推导几次后总结了一个记忆方法每轮循环只往队列里塞一个新的左端点候选就是当前右端点r对应最小合法长度a的那个左端点然后查询所有可能左端点中pre值最小的那个。队列里存的是pre值递增的下标队头有效且最小。最后再分享一个小技巧在本地提交前先跑一遍ab的退化用例和全负数组用例这两个用例能过滤掉绝大多数边界bug。踩过几次坑之后这类“窗口长度约束前缀最值”的题会变得非常稳定属于看一遍就知道解法模板的题型。