P1121 环状最大两段子段和

题目描述

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

输入输出格式

输入格式：

输入文件maxsum2.in的第一行是一个正整数N $(N\le 2\times 10^{5})(N≤2×105)，表示了序列的长度。$

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

输出格式：

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

输入输出样例

输入样例#1：

72 -4 3 -1 2 -4 3

输出样例#1：

说明

【样例说明】

一段为3

分析：

环变链的方法不行，环变链以后，DP求出来的最大值序列长度不定，两个区间可能重复。

那么只能在原有的序列上做了。

答案无非两种情况：

（假装是图示：0不选，+选）

情况1：000+++++++000000+++++000000

情况2:+++++000000+++++000000+++++

以上都是环，也就是说左右端点相连。

可以看出，情况1的最优解就是在原序列上求两个和最大的子段。

情况2的最优解就是在原序列上求两个和最小的子段，用总和减一下。

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 using namespace std; 9 const int mxn=200010;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 int n;17 int a[mxn];18 int f1[mxn],f2[mxn],d1[mxn],d2[mxn];19 int smm=0;20 int main(){21 int i,j;22 //读取数据 23 n=read();24 for(i=1;i<=n;i++)a[i]=read(),smm+=a[i];25 int nmx=-1e9,nmi=1e9;26 f1[0]=-1e9;d1[0]=1e9;27 //从前往后求28 //f1[]是最大的子段，d1[]是最小的子段 29 for(i=1;i<=n;i++){30 nmx=max(nmx+a[i],a[i]);31 nmi=min(nmi+a[i],a[i]);32 f1[i]=max(f1[i-1],nmx);33 d1[i]=min(d1[i-1],nmi);34 }35 nmx=-1e9;nmi=1e9;36 f2[n+1]=-1e9;d2[n+1]=1e9;37 //从后往前求38 //f2[]是最大的子段，d2[]是最小的子段 39 for(i=n;i;i--){40 nmx=max(nmx+a[i],a[i]);41 nmi=min(nmi+a[i],a[i]);42 f2[i]=max(f2[i+1],nmx);43 d2[i]=min(d2[i+1],nmi);44 }45 //46 int ans=-1e9;47 for(i=1;i