题目描述

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

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

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

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

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

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

数据范围
1≤n,m≤300000

样例

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

单调队列：查找O（1），维护O（n）（比较经典的数据结构）

1）用队列维护集合
2）把没用的元素删掉（若当前数比前一个数小或者等于，就把队列里的元素删掉，直到小于这个数为止）
3）队列单调
4）O（1）找min,max

C++ 代码

#include<iostream>
#include<algorithm>
#include<limits.h> 
using namespace std;
typedef long long ll;
const int N=300010;
ll s[N]; 
ll q[N];//单调队列 
int main(){

        int n,m;
        cin>>n>>m;
         for(int i=1;i<=n;i++){
            cin>>s[i];
            s[i]+=s[i-1];
         }  
         int hh=0,tt=0;
         ll res=INT_MIN;
         //求最大子序列的和，即求以s[i]减去s[i]前面m个数中的最小值

         for(int i=1;i<=n;i++){//枚举i为右端点，看i前面的数j，维护长度为m的队列
            if(i-q[hh]>m)hh++;//长度大于n-1就出队 
            res=max(res,s[i]-s[q[hh]]);
            while(hh<=tt&&s[q[tt]]>=s[i])tt--;//若当前数比前一个数小或者等于，
                                              // 就把队列里的元素删掉，直到小于这个数为止 （维护队列的单调性） 
            q[++tt]=i;// 把当前数插入队列 
         }
       cout<<res;








    return 0;
}