最大子序和II

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

输入格式

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

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

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

输出格式

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

数据范围

1≤n,m≤300000

输入样例：

6 4 1 -3 5 1 -2 3

输出样例：

7 算法：单调队列 #include<iostream>#include<queue>#include<algorithm>#include<limits.h>using namespace std;const int N=300010;typedef long long LL;LL s[N];int n,m;deque<int>q;int main(void){    cin>>n>>m;    for(int i=1;i<=n;i++){        cin>>s[i];        s[i]+=s[i-1];    }    q.push_back(0);    LL res=INT_MIN;    for(int i=1;i<=n;i++){        if(i-q.back()>m)q.pop_back();        res=max(res,s[i]-s[q.back()]);        while(q.size()&&s[q.front()]>=s[i])q.pop_front();        q.push_front(i);    }    cout<<res<<endl;    return 0;}

 

转载于:https://www.cnblogs.com/programyang/p/11209049.html