前缀和&&单调队列：最大子序和

输入一个长度为 nn 的整数序列，从中找出一段长度不超过 mm 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 11。

输入格式

第一行输入两个整数 n,mn,m。

第二行输入 nn 个数，代表长度为 nn 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

1≤n,m≤3000001≤n,m≤300000

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

题解：

这道题可以用for循环，但是当数据量过大时会运行时间过长，所以用到了单调队列。

单调队列的题以及模板如下：

单调队列 —— 模板题 AcWing 154. 滑动窗口
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

 

本题代码如下：

#include 

using namespace std;

typedef long long LL;

const int N = 3e5 + 10;

int n, m;
LL s[N], que[N];

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ )
    {
        cin>>s[i];
        s[i] += s[i - 1];//前缀和
    }
    LL res = -1e18;
    int hh = 0, tt = 0;
    que[0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && i - que[hh] > m) //单调队列，当队首元素的序列与i相差超过m，队首元素出队
            hh ++ ;
        res = max(res, s[i] - s[que[hh]]);
        while (hh <= tt && s[que[tt]] >= s[i]) //单调队列，当队尾元素大于当前元素s[i]，队尾元素出队
            tt -- ;
        que[ ++ tt] = i;//当前元素入队
    }
    cout<