P1121 环状最大两段子段和

时间:2021-12-31 10:39:42

P1121 环状最大两段子段和

题目描述

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:
7
2 -4 3 -1 2 -4 3
输出样例#1:
9

说明

【样例说明】

一段为3

分析:

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

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

答案无非两种情况:

(假装是图示:0不选,+选)

情况1:000+++++++000000+++++000000

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

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

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

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

 /*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n;
int a[mxn];
int f1[mxn],f2[mxn],d1[mxn],d2[mxn];
int smm=;
int main(){
int i,j;
//读取数据
n=read();
for(i=;i<=n;i++)a[i]=read(),smm+=a[i];
int nmx=-1e9,nmi=1e9;
f1[]=-1e9;d1[]=1e9;
//从前往后求
//f1[]是最大的子段,d1[]是最小的子段
for(i=;i<=n;i++){
nmx=max(nmx+a[i],a[i]);
nmi=min(nmi+a[i],a[i]);
f1[i]=max(f1[i-],nmx);
d1[i]=min(d1[i-],nmi);
}
nmx=-1e9;nmi=1e9;
f2[n+]=-1e9;d2[n+]=1e9;
//从后往前求
//f2[]是最大的子段,d2[]是最小的子段
for(i=n;i;i--){
nmx=max(nmx+a[i],a[i]);
nmi=min(nmi+a[i],a[i]);
f2[i]=max(f2[i+],nmx);
d2[i]=min(d2[i+],nmi);
}
//
int ans=-1e9;
for(i=;i<n;i++){
//两个最大的子段
ans=max(ans,f1[i]+f2[i+]);
//两个两个最小的子段
if(smm-d1[i]-d2[i+])ans=max(ans,smm-d1[i]-d2[i+]);
}
cout<<ans<<endl;
return ;
}