在处理“连续区间和”问题时前缀和是我们最常用的武器。但如果题目加上了“区间长度必须在 [l,r] 之间”的死命令传统的 O(N^2) 暴力枚举就会瞬间超时。今天我们用单调队列这把尖刀从“正向”和“逆向”两个极端的视角把这道极其经典的滑动窗口问题彻底扒光实现 O(N) 的降维打击。一、 题目描述【题目大意】给你 n 个数 a1,a2,…,an 和两个数 l,r。你需要在这 n 个数中选出一段连续区间的数满足区间长度 ∈[l,r]。 求出满足条件的最大连续区间和。【样例输入】8 1 2 -1 3 -2 5 3 -5 2 2【样例输出】8【数据范围】1≤l≤r≤n≤200000 −10^9≤a[i]≤10^9二、 题目分析与解题思路求区间和的第一反应必须是前缀和。设S[i]为前i个元素的和。 任意一段以L为起点、R为终点的区间和可以转化为S[R]−S[L−1]。既然要让差值最大我们有两种截然不同的战术思路战术一固定起点向未来找最高售价假设买入成本S[L−1]已固定我们在合法的未来窗口内找一个最大的卖出价S[R]。战术二固定终点向历史找最低成本假设卖出价S[R]已固定我们在合法的历史窗口内找一个最小的买入成本S[L−1]。这两种战术对应了两种双指针滑动的写法。三、 算法设计与思考过程做法一固定起点正向找最大终点外层循环枚举起点i也就是公式里的 L范围是从1到n−l1。侦察兵x代表终点R。它从最短合法距离xL开始一路向右扫描。单调队列维护我们要找最大的S[x]所以维护一个单调递减队列。遇到前缀和比自己大、且寿命更长的新人队尾的老将直接被物理抹杀。过期清理合法终点至少要达到il−1。如果队首的老将距离起点太近直接踢出队列。做法二固定终点逆向找最小起点外层循环枚举终点i公式里的R采用逆向倒序从n一路退到L。侦察兵 x代表被减数的位置起点的前一位 L−1。它从最靠右的合法位置xn−l开始一路向左退。单调队列维护我们要找最小的成本S[x]所以维护一个单调递增队列。遇到成本更低的新人队尾老将出队。逆向过期逻辑全场最核心因为我们是从右往左扫描先入队的老将其坐标x大于后入队的新人。当终点 i 不断向左退时右边的老将就会变成“距离终点太近”的违规品。因此过期条件是q[front]i-l。四、 易错点总结极小值初始化最大和ma不能初始化为0。如果数组全是负数答案也会是负数。必须初始化为极小值如-1e18。循环的精确边界* 正向写法的起点边界最大只能走到n-l1多一步都走不了。逆向写法的终点边界最小只能退到l退到l−1就凑不够长度l了。前缀和的-1障眼法单调队列里存的到底是谁在做法二中侦察兵x本身代表的就是“起点的前一位”所以结算时直接用s[i]-s[q[front]]即可绝对不能再去写s[q[front]-1]否则会发生下标漂移。五、 时空复杂度分析时间复杂度O(N)。无论是正向还是逆向外层指针和内层侦察兵 x 都是单向行驶、绝不回头的。每个下标最多入队一次、出队一次均摊复杂度严格为O(N)。空间复杂度O(N)。需要开辟长度为N的前缀和数组S以及单调队列数组q。六、 完整代码解法一固定起点从左往右扫描维护递减队列//最大连续区间和 先求前缀和 //先求前缀和然后两种做法 1固定起点 找满足区间长度要求值最大终点 //2固定终点找满足区间长度要求值最小起点 //这里先写第一种做法 #include iostream #include algorithm//对应min max函数 using namespace std; int n,l,r; long long s[200010];//前缀和数组 int q[200010];//队列 int front1,rear0;//队首 队尾 long long ma-1e18;//初始化最大连续区间和为极小值 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnlr; //求前缀和数组 for(int i1;in;i){ int x; cinx; s[i]s[i-1]x; } //x为终点起点从1开始终点最小为L才能满足区间长度不小于L int xl; //i代表起点从1开始最大为n-l1 for(int i1;in-l1;i){ //ir-1是满足区间长度要求终点最大值不能超过这个范围 //n是终点最大值 while(xir-1xn){ //如果当前队列非空 //且当前终点的值(x)大于等于队尾的值队尾元素出队 //因为队尾元素既不大于x又更老未来不可能用到 while(frontrears[x]s[q[rear]]){ rear--; } //直到队列为空或x小于队尾元素 //把x入队 q[rear]x; x; } //接下来判断队首是否已经过期不满足区间长度要求 //如果已经过期就队首出队 //il-1是终点至少要大于等于这个值才满足区间长度要求 //即没过期 while(q[front]il-1) front; //队首就是区间内最大值 mamax(ma,s[q[front]]-s[i-1]); } coutma; return 0; }解法二固定终点从右往左逆向扫描维护递增队列//最大连续区间和 先求前缀和 //先求前缀和然后两种做法 1固定起点 找满足区间长度要求值最大终点 //2固定终点找满足区间长度要求值最小起点 //这里写第二种做法 #include iostream using namespace std; int n,l,r; long long s[200010];//前缀和数组 int q[200010];//队列 存最小起点 int front1,rear0;//队首 队尾 long long ma-1e18; int main(){ cinnlr; //求前缀和 for(int i1;in;i){ int x; cinx; s[i]s[i-1]x; } //起点从n-L1开始(当终点为n时起点至多是n-L1才能满足区间长度要求 //但是求终点和起点之间的和要用终点-起点前面一位 //起点前面一位是n-L int xn-l; //i代表终点从右往左终点至少要大于等于L才能满足区间长度最小要求 for(int in;il;i--){ //当起点前一位不小于能取到的最小值且起点满足区间长度要求时 while(x0xi-r){ //如果x比队尾更小就把队尾出队 //因为老队尾值又大进栈时间又早再也不会被后面使用到 while(frontrears[x]s[q[rear]]){ rear--; } //当队列为空或x大于队尾元素时 q[rear]x; x--; } //把过期队首出队 while(q[front]i-l) front; mamax(ma,s[i]-s[q[front]]); } coutma; return 0; }
Maximum Subarray Sum II最大连续区间和（CSES- P1644）
在处理“连续区间和”问题时前缀和是我们最常用的武器。但如果题目加上了“区间长度必须在 [l,r] 之间”的死命令传统的 O(N^2) 暴力枚举就会瞬间超时。今天我们用单调队列这把尖刀从“正向”和“逆向”两个极端的视角把这道极其经典的滑动窗口问题彻底扒光实现 O(N) 的降维打击。一、 题目描述【题目大意】给你 n 个数 a1,a2,…,an 和两个数 l,r。你需要在这 n 个数中选出一段连续区间的数满足区间长度 ∈[l,r]。 求出满足条件的最大连续区间和。【样例输入】8 1 2 -1 3 -2 5 3 -5 2 2【样例输出】8【数据范围】1≤l≤r≤n≤200000 −10^9≤a[i]≤10^9二、 题目分析与解题思路求区间和的第一反应必须是前缀和。设S[i]为前i个元素的和。 任意一段以L为起点、R为终点的区间和可以转化为S[R]−S[L−1]。既然要让差值最大我们有两种截然不同的战术思路战术一固定起点向未来找最高售价假设买入成本S[L−1]已固定我们在合法的未来窗口内找一个最大的卖出价S[R]。战术二固定终点向历史找最低成本假设卖出价S[R]已固定我们在合法的历史窗口内找一个最小的买入成本S[L−1]。这两种战术对应了两种双指针滑动的写法。三、 算法设计与思考过程做法一固定起点正向找最大终点外层循环枚举起点i也就是公式里的 L范围是从1到n−l1。侦察兵x代表终点R。它从最短合法距离xL开始一路向右扫描。单调队列维护我们要找最大的S[x]所以维护一个单调递减队列。遇到前缀和比自己大、且寿命更长的新人队尾的老将直接被物理抹杀。过期清理合法终点至少要达到il−1。如果队首的老将距离起点太近直接踢出队列。做法二固定终点逆向找最小起点外层循环枚举终点i公式里的R采用逆向倒序从n一路退到L。侦察兵 x代表被减数的位置起点的前一位 L−1。它从最靠右的合法位置xn−l开始一路向左退。单调队列维护我们要找最小的成本S[x]所以维护一个单调递增队列。遇到成本更低的新人队尾老将出队。逆向过期逻辑全场最核心因为我们是从右往左扫描先入队的老将其坐标x大于后入队的新人。当终点 i 不断向左退时右边的老将就会变成“距离终点太近”的违规品。因此过期条件是q[front]i-l。四、 易错点总结极小值初始化最大和ma不能初始化为0。如果数组全是负数答案也会是负数。必须初始化为极小值如-1e18。循环的精确边界* 正向写法的起点边界最大只能走到n-l1多一步都走不了。逆向写法的终点边界最小只能退到l退到l−1就凑不够长度l了。前缀和的-1障眼法单调队列里存的到底是谁在做法二中侦察兵x本身代表的就是“起点的前一位”所以结算时直接用s[i]-s[q[front]]即可绝对不能再去写s[q[front]-1]否则会发生下标漂移。五、 时空复杂度分析时间复杂度O(N)。无论是正向还是逆向外层指针和内层侦察兵 x 都是单向行驶、绝不回头的。每个下标最多入队一次、出队一次均摊复杂度严格为O(N)。空间复杂度O(N)。需要开辟长度为N的前缀和数组S以及单调队列数组q。六、 完整代码解法一固定起点从左往右扫描维护递减队列//最大连续区间和 先求前缀和 //先求前缀和然后两种做法 1固定起点 找满足区间长度要求值最大终点 //2固定终点找满足区间长度要求值最小起点 //这里先写第一种做法 #include iostream #include algorithm//对应min max函数 using namespace std; int n,l,r; long long s[200010];//前缀和数组 int q[200010];//队列 int front1,rear0;//队首 队尾 long long ma-1e18;//初始化最大连续区间和为极小值 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnlr; //求前缀和数组 for(int i1;in;i){ int x; cinx; s[i]s[i-1]x; } //x为终点起点从1开始终点最小为L才能满足区间长度不小于L int xl; //i代表起点从1开始最大为n-l1 for(int i1;in-l1;i){ //ir-1是满足区间长度要求终点最大值不能超过这个范围 //n是终点最大值 while(xir-1xn){ //如果当前队列非空 //且当前终点的值(x)大于等于队尾的值队尾元素出队 //因为队尾元素既不大于x又更老未来不可能用到 while(frontrears[x]s[q[rear]]){ rear--; } //直到队列为空或x小于队尾元素 //把x入队 q[rear]x; x; } //接下来判断队首是否已经过期不满足区间长度要求 //如果已经过期就队首出队 //il-1是终点至少要大于等于这个值才满足区间长度要求 //即没过期 while(q[front]il-1) front; //队首就是区间内最大值 mamax(ma,s[q[front]]-s[i-1]); } coutma; return 0; }解法二固定终点从右往左逆向扫描维护递增队列//最大连续区间和 先求前缀和 //先求前缀和然后两种做法 1固定起点 找满足区间长度要求值最大终点 //2固定终点找满足区间长度要求值最小起点 //这里写第二种做法 #include iostream using namespace std; int n,l,r; long long s[200010];//前缀和数组 int q[200010];//队列 存最小起点 int front1,rear0;//队首 队尾 long long ma-1e18; int main(){ cinnlr; //求前缀和 for(int i1;in;i){ int x; cinx; s[i]s[i-1]x; } //起点从n-L1开始(当终点为n时起点至多是n-L1才能满足区间长度要求 //但是求终点和起点之间的和要用终点-起点前面一位 //起点前面一位是n-L int xn-l; //i代表终点从右往左终点至少要大于等于L才能满足区间长度最小要求 for(int in;il;i--){ //当起点前一位不小于能取到的最小值且起点满足区间长度要求时 while(x0xi-r){ //如果x比队尾更小就把队尾出队 //因为老队尾值又大进栈时间又早再也不会被后面使用到 while(frontrears[x]s[q[rear]]){ rear--; } //当队列为空或x大于队尾元素时 q[rear]x; x--; } //把过期队首出队 while(q[front]i-l) front; mamax(ma,s[i]-s[q[front]]); } coutma; return 0; }
