P1121 环状最大两段子段和(DP)

P1121 环状最大两段子段和

难度 提高+/省选-

题目描述

给出一段环状序列，即认为A[1]和A[N]是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。

输入输出格式

输入格式：

输入文件maxsum2.in的第一行是一个正整数N，表示了序列的长度。

第2行包含N个绝对值不大于10000的整数A[i]，描述了这段序列，第一个数和第N个数是相邻的。

输出格式：

输入文件maxsum2.out仅包括1个整数，为最大的两段子段和是多少。

输入输出样例

输入样例#1：

7

2 -4 3 -1 2 -4 3

输出样例#1：

9

说明

【样例说明】

一段为3

/*

DP.

最大子段和问题.

n^2的做法是

拆成链对每一个区间维护最大前缀/后缀和.

然后枚举断点.

这个很好想但过不了so没打(懒~).

看了看题解orz.

恩o(n).

最大子段和无非就有两种情况.

(1)跨区间的.

(2)在[1,n]中的.

然后难搞的可能是(1).

然后我们换个思路.

我们在[1,n]中求一个最小前缀/后缀和.

然后用sum减去即可.

正确性是显然的.

因为求最小的时候我们默认包括[i,i+1].

这段不选的最小子段区间必定是连续的.

故选的必定为1段(如果选的是[1,i],[i+1,n]这一段

我们也可以认为它们是分开选的两段).

*/

#include<iostream>

#include<cstdio>

#define MAXN 200001

using namespace std;

int maxl[MAXN],maxr[MAXN],minl[MAXN],minr[MAXN],n,s[MAXN],sum,ans=-1e9,max1,min1;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

int main()

{

    n=read();

    for(int i=1;i<=n;i++) s[i]=read(),sum+=s[i];

    maxl[1]=minl[1]=max1=min1=s[1];

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

    {

        if(max1>0) max1+=s[i];

        else max1=s[i];

        if(min1<0) min1+=s[i];

        else min1=s[i];

        maxl[i]=max(maxl[i-1],max1);

        minl[i]=min(minl[i-1],min1);

    }

    maxr[n]=minr[n]=max1=min1=s[n];

    for(int i=n-1;i>=1;i--)

    {

        if(max1>0) max1+=s[i];

        else max1=s[i];

        if(min1<0) min1+=s[i];

        else min1=s[i];

        maxr[i]=max(maxr[i+1],max1);

        minr[i]=min(minr[i+1],min1);

    }

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

    {

        ans=max(ans,maxl[i]+maxr[i+1]);

        if(sum-minl[i]-minr[i+1]) ans=max(ans,sum-minl[i]-minr[i+1]);

    }

    printf("%d",ans);

    return 0;

}

巴特西

P1121 环状最大两段子段和(DP)

最新文章

热门文章