| |
|
|
| |
描述 Description |
|
| |
输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。
例如 1，-3,5,1，-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6 |
| |
|
|
| |
|
|
| |
输入格式 Input Format |
|
| |
第一行两个数n,m
第二行有n个数，要求在n个数找到最大子序和 |
| |
|
|
| |
|
|
| |
输出格式 Output Format |
|
| |
一个数，数出他们的最大子序和 |
| |
|
|
| |
|
|
| |
时间限制 Time Limitation |
|
| |
各个测试点1s |
| |
|
|
| |
|
|
| |
注释 Hint |
|
| |
数据范围：
100%满足n,m<=300000 |
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=301000;
int a[N],sum[N];
int Q[N],I[N];//最小单调队列
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}
int head=0,tail=-1;
int _max=(1<<31);
for(int j=1;j<=n;j++)//sum[j]-sum[i-1]的最大值
{
int i=j-1;//sum[j-1]入队
while(head<=tail&&Q[tail]>=sum[i]) tail--;
tail++;
Q[tail]=sum[i],I[tail]=i;
i=j-m-1;//sum[i]出队
while(head<=tail&&I[head]<=i) head++;
int _res=sum[j]-Q[head];
if(_res>_max) _max=_res;
}
printf("%d/n",_max);
}
return 0;
}