题解 P1115 【最大子段和】单调队列介绍

· · 题解

翻到底发现竟然没有单调队列的题解。

最大子序列和是一道经典的单调队列题，其模型常用不亚于滑动窗口。

从本题切入

本题是一道极其简单的题目。

子序和就是两个前缀和的差值，当我们确定了子序列的右端点j之后我们就得到了子问题找到最佳的左端点i使子序列和最小。

即

ans=min\left\{ sum[j] - min \left\{sum[\space i-1\space],\space\space i\in[\space 1, j\space)\space \right\},\space\space j \in [1,n]\space\right\}

这个问题显然可以O(n^2)地得到解决方案，但是为了通过2e5的数据我们需要一个更快的算法。

通过简单地观察我们可以发现对于子问题min \left\{sum[\space i-1\space],\space\space i\in[\space 1, j\space)\space \right\}我们或许不需要用一个循环枚举所有的决策，对于我们有价值的只有最后一个决策点k，使得sum[k]在所有符合要求的决策中最小/最优。

如果我们不断地更新i之前的最优决策，那么我们就可以直接O(1)地求出子问题的解，所以总复杂度就是n个子问题加起来也就是O(n)的。

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 2e5 + 10;
int n, m, ans = 0x80000000, sum[maxn], a, choice = 0x7fffffff;
int main(){
    cin >> n ;
    m = n;
    for(int i = 1; i <= n; i++){
        cin >> a;
        sum[i] = sum[i-1] + a;
        choice = min(sum[i-1], choice);//得到i之前的最优决策
        ans = max(ans, sum[i] - choice);//选出当前最优决策
    }
    cout << ans << endl;
    return 0;
}

如果你只是想知道怎么做这题，或者你不知道队列是什么，那么看到这里就够了。

单调队列

让我们思考一下这题的升级版，如果我们限制了子序列的长度不得超过m那么又该怎么做？

还是先之前一样，抽象出问题模型。

ans=min\left\{ sum[j] - min \left\{sum[\space i-1\space],\space\space i\in[\space j-m, j\space)\space \right\},\space\space j \in [1,n]\space\right\}

与上一个问题不同，因为此题中我们增加了长度限制，所以我们不能故伎重演，直接保存i之前的最优决策。

由于我们直接保存的最优决策的决策点k可能超出了长度限制，所以我们需要的是长度限制内的最优决策点，那么对于超出了长度限制的，过期了的决策我们就可以抛弃。那么如何维护一个这样的最优决策呢？

介绍单调队列

这是一种特殊的队列，可以同时从队首和队尾出队，一般我们用它来维护一个队列的单调性，如果决策的最优性不单调，我们就通过队尾出队的方式来保证队列中的元素单调，并通过队头出队抛弃过期的决策。

而在子序列和的问题中我们知道一个决策点的前缀和越小，则这个决策越优，那么如果在我们储存的决策点中，如果有一个决策点k2之前存在一个决策点k1 < k2满足sum[k1] > sum[k2]，显然k1不是一个优秀的决策，因为k1距离更远，而不够优秀，所以当我们取到了k2我们就可以抛弃k1这个决策。根据题目的这个性质我们就可以维护单调队列，使得队中决策点下标位置递增，且前缀和也是递增，这就像有了一个更好看也更爱你的异性你就可以适时地抛弃之前那个价值不够高的选择。

上代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 2e5 + 10;
int n, m, ans = 0x80000000, sum[maxn], a;
deque<int> Q;//用于存储决策
//单调队列算法首先证明决策在满足某种单调性的前提下可以使得答案更优的情况，然后抛弃不优的决策，在这里就是选尽量靠前的sum小的决策
int main(){
    cin >> n >> m;
    Q.push_back(0);//存入初始决策，即左端点为1的情况
    for(int i = 1; i <= n; i++){
        cin >> a;
        sum[i] = sum[i-1] + a;
        while(!Q.empty() && Q.front() < i - m) Q.pop_front();//抛弃过期的决策
        cerr << sum[i] - sum[Q.front()] << endl;
        ans = max(ans, sum[i] - sum[Q.front()]);//选出当前最优决策
        while(!Q.empty() && sum[Q.back()] > sum[i]) Q.pop_back();//维护决策的单调性
        Q.push_back(i);
    }
    cout << ans << endl;
    return 0;
}

这样我们就可以得到一个O(n)的算法了。

复杂度证明：每个点只会入队出队一次，所以是O(n)的。

更多应用

在学习单调队列的过程中我们发现了单调队列可以维护一个区间内的最优策略。不仅仅是区间min，sum这种简单的操作还有更多的骚操作，比如进行一些DP决策单调性的优化（如多重背包）（男人八题.jpg

撒花????