【集训Day3 单调队列】【2018寒假集训Day 5更新】最大子序列和

最大子序列和（maxsum）
【问题描述】
输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。
例如：
序列 1， -3， 5， 1， -2， 3
当M=2或3时，S=5+1=6；当M=4时，S=5+1+(-2)+3=7。
【输入格式】
输入文件第一行一个整数n表示序列的长度，第二行n个整数，代表序列的元素。第三行一个整数表示M。
【输出格式】
一个整数，即子序列的最大和。保证结果不超过longint范围。
【输入样例】
6
1 -3 5 1 -2 3
3
【输出样例】
6
【数据范围】
50%的数据N,M<=1000
100%的数据N,M<=20000
【解题思路】
求出前缀和后，a[i]+a[i+1]……+a[j]就可以用sum（前缀和数组）[j]-sum[i]+a[i]得出，那么我们只需要让j-i+1<=m同时让sum[j]最大，而j的范围可以是i+1、i+2…i+m-1,那么就变成了一个求出固定区间长度为m的最大值。

更正：求出前缀和后，a[i-m+1]+a[i-m+2]……+a[i]就可以用sum（前缀和数组）[i]-sum[i-m]得出，那么我们只需要在这个区间里寻找最小的sum[j]，j的范围是i-m+1<=j<=i,那么就变成了一个求出长度为m的固定区间的最大值。
【解题反思】

队列中不必要存入数据，可以存入下标。
在判断队头是否在区间内时，求出队列长度不是用尾指针的值减去头指针。用队列中尾指针指向的位置减去头指针指向的位置加上1的值才是队列长度。

【参考程序】

#include<iostream>

#include<cstdio>

using namespace std;

int n,m,a[200001];

int sum[200001],b[200001],maxans;

int main()

{

    freopen("maxsum.in","r",stdin);

    freopen("maxsum.out","w",stdout);

    scanf("%d",&n);

    for (int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

        sum[i]=sum[i-1]+a[i];

    }

    scanf("%d",&m);

    int head=1,tail=1,i=1;

    while (i<=n)

    {

        while (sum[i]<=sum[b[tail]]&&tail>=head)

            tail--;

        tail++;

        b[tail]=i;

        if (b[tail]-b[head]+1>m&&head<tail) head++;

        maxans=max(maxans,sum[i]-sum[b[head]]);

        i++;

    }

    cout<<maxans;

    return 0;

}

巴特西

【集训Day3 单调队列】【2018寒假集训Day 5更新】最大子序列和

最新文章

热门文章