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的最優解就是在原序列上求兩個和最小的子段，用總和減一下。

?

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 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<n;i++){ 48 //兩個最大的子段 49 ans=max(ans,f1[i]+f2[i+1]); 50 //兩個兩個最小的子段 51 if(smm-d1[i]-d2[i+1])ans=max(ans,smm-d1[i]-d2[i+1]); 52 } 53 cout<<ans<<endl; 54 return 0; 55 }

?

轉載于:https://www.cnblogs.com/Renyi-Fan/p/7429408.html

總結

以上是生活随笔為你收集整理的P1121 环状最大两段子段和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。