题目描述

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

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

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

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

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

数据范围
$1≤n,m≤300000$

样例

输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7

单调队列 $O(N)$

重新写一遍。。。

计算区间和，我们很容易想到前缀和，也就是说我们要查询$[l,r]$区间的值，我们显然会这样处理。

$sum[r]-sum[l-1] \quad sum[i]表示[1,i]的和$

这句话就是我们非常熟悉的前缀和求区间和。

那么这道题目如何处理呢？

我们发现我们的目标就是

找到两个位置$l,r$,要求

1. $r-l \le M$ 也就是说区间的大小不可以超过$M$
2. $sum[r]-sum[l]$ 尽量大.

这么说来，我们完全可以$O(n^2)$枚举$l,r$不就好了吗？

但是时间复杂度说：臣妾做不到

所以说，我们只能够通过单调队列来处理这道题目了。

单调队列是什么，欢迎阅读博主的文章

我们着重理解一下如何单调队列。

我们发现假如说我们的右端点$r$，固定好了，那么我们的问题就变化了。

找到一个左端点$l$，要求$j \in {[i-m,i-1]}$.

这句话的意思就是说，我们这个区间长度不可以超过$m$,而且区间长度至少为$1$. 这不是废话嘛

而且呢$sum[j]$要尽量的小，为了使得区间和最大，对吧。

所以说咱们发现，这个$j$的取值，是一个区间，而且最主要的是，我们只要这个区间的最值。

区间最值，就可以通过单调队列处理。

我们发现如果说有一个位置$k$，这个$k<j<i$.而且$sum[k] \ge sum[j]$

用人话说就是，一个人比你先学习，也就是比你老，而且实力还不如你，那么请问这个人打得赢你吗？

对不起，实力不允许，蒟蒻我打赢大佬你。

我们来理性分析一遍。

$k<j$，也就是说$[k,i]$这个区间的长度，一定是大于$[j,i]$这个区间长度的。

$sum[k] \ge sum[j]$，这么说来的话，那么$sum[i]-sum[k] \ge sum[i]-sum[j]$，也就是说我们的[k,j]区间消耗更大。

既然如此，那么$k$是真的很菜，是真的没有用了。

我们的$j$，不仅比$k$更加接近$i$，最主要的是，消耗比$k$小。

那么我们还有什么理由选择$k$呢。

一个机器，我们当然是选择，又新，消耗又少的，肯定不会选择又老，还消耗大的。

绿色蓝天，从我做起。—公益广告

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=300100;
deque<long long> q;
long long n,m,l,r,s[N],a[N],ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    fir(i,1,n)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    fir(i,1,n)
    {
        while(q.size() && q.front()<i-m)//如果队头已经无法满足区间长度小于m的话,那么弹出
            q.pop_front();//队头不满足,不需要,弹出.
        ans=max(ans,s[i]-s[q.front()]);//取当前最优值
        while(q.size() && s[q.back()]>=s[i])//如果说队尾大于当前值的话.
            q.pop_back();//不需要,弹出
        q.push_back(i);//将i放入队尾.
    }
    cout<<ans;
    return 0;
}