最大子序和单调队列

最大子序和

Time Limit: 1 Sec Memory Limit: 256 MB

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

第一行两个数n,m（1<=n,m<=300000）第二行有n个数，要求在n个数找到最大子序和。

Output

一个数，即最大子序和S（S值不超过long long int）。

Sample Input

6 4

1 -3 5 1 -2 3

Sample Output

7

分析：

若 k < i < j,且 s[k] > s[i],则 s[j] - s[i] > s[j] - s[k],即 a[i] +...+ a[j] > a[k] + ... + a[j]

所以只需要枚举j,并找到每段区间中的最小值s[i]即可

int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[i] = s[i-1] + a[i];
//s[i] = a[1] + ... + a[i]; 
int l = 1,r = 1; // 维护队列左右边界 
q[l] = 0;//q 单调队列 存下标 

ans = -0xfffffff;// ans初始化为极小值
for(int i=1;i<=n;i++)
{
    while(l<=r && q[l]<i-m) l++;
    ans = max(ans,s[i] - s[q[l]]);
    while(l<=r && s[q[r]]>s[i]) r--;
    q[++r] = i;
}
    
printf("%lld",ans);

WA原因：

思路是长度为m的区间内的最大值减最小值，然后再判断一下最值的下标关系。实际上这样的贪心思路有可能出错。

况且单减的数据会出问题。

附WA代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<cstring>
#define sizen 300050
using namespace std;
struct node
{
    int number,order;
};
long long int num[sizen]={0};
int v[sizen];
node maxx[sizen],minn[sizen];
node q[sizen];
int main()
{
    //freopen("sum.in","r",stdin);
    //freopen("sum.out","w",stdout);
    
    int n,m,head = 0,tail = 0;
    long long int ans = 0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    
    for(int i=1;i<=n;i++)
    num[i] = num[i-1] + v[i];
     
    for(int i=0;i<=m;i++)
    {
        if(i == 0)q[tail].number = num[i],q[tail++].order = i;
        else
        {
            while(head != tail && q[tail-1].number < num[i])tail--;
            q[tail].number = num[i],q[tail++].order = i;
        }
        maxx[i].number = q[head].number,maxx[i].order = q[head].order;
    }
    
    for(int i=m+1;i<=n;i++)
    {
        while(head != tail && q[tail - 1].number < num[i])tail--;
        q[tail].number = num[i],q[tail++].order = i;
        if(q[head].number == num[i - m - 1])head++;
        maxx[i].number = q[head].number,maxx[i].order = q[head].order;
    }
    
    head = 0;
    tail = 0;
    for(int i=0;i<=m;i++)
    {
        if(i == 0)q[tail].number = num[i],q[tail++].order = i;
        else
        {
            while(head != tail && q[tail-1].number > num[i])tail--;
            q[tail].number = num[i],q[tail++].order = i;
        }
        minn[i].number = q[head].number,minn[i].order = q[head].order;
    }
    for(int i=m+1;i<=n;i++)
    {
        while(head != tail && q[tail - 1].number > num[i])tail--;
        q[tail].number = num[i],q[tail++].order = i;
        if(q[head].number == num[i - m - 1])head++;
        minn[i].number = q[head].number,minn[i].order = q[head].order;
    }
    

    for(int i=0;i<=n;i++)
    {
        if(maxx[i].order >= minn[i].order && maxx[i].number - minn[i].number > ans)
        ans = maxx[i].number - minn[i].number;
    }
    
    printf("%lld",ans);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

最大子序和 单调队列