N个整数组成的序列a[1],a[2],a[3],…,a[n]，你可以对数组中的一对元素进行交换，并且交换后求a[1]至a[n]的最大子段和，所能得到的结果是所有交换中最大的。当所给的整数均为负数时和为0。
例如：{-2,11,-4,13,-5,-2, 4}将 -4 和 4 交换，{-2,11,4,13,-5,-2, -4}，最大子段和为11 + 4 + 13 = 28。
Input
第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
Output
输出交换一次后的最大子段和。
先考虑与左边的数字交换的情况。
枚举交换位置x，把交换后的段拆成x左边和x右边两部分算。
需要事先计算出前缀和、后缀和、后缀和的后缀最小值、（前缀和 - 前缀最大值）的前缀最小值。
和右边的数交换同理。。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 #define ll long long 8 #define ui unsigned int 9 #define ull unsigned long long 10 using namespace std; 11 const int maxn=50023,modd=1000000007; 12 ll mn1[maxn],mn2[maxn],_mn1[maxn],_mn2[maxn],pr[maxn],af[maxn],ans; 13 int prmx[maxn],afmx[maxn],a[maxn]; 14 int i,j,k,n,m; 15 16 int ra,fh;char rx; 17 inline int read(){ 18 rx=getchar(),ra=0,fh=1; 19 while((rx<'0'||rx>'9')&&rx!='-')rx=getchar(); 20 if(rx=='-')fh=-1,rx=getchar(); 21 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh; 22 } 23 24 int main(){ 25 n=read();prmx[0]=afmx[n+1]=-1e9; 26 for(i=1;i<=n;i++)a[i]=read(),pr[i]=pr[i-1]+a[i],prmx[i]=max(prmx[i-1],a[i]); 27 for(i=n;i;i--)af[i]=af[i+1]+a[i],afmx[i]=max(afmx[i+1],a[i]); 28 29 // mn1[1]=0,mn2[1]=pr[1]; 30 for(i=1;i<=n;i++) 31 mn1[i]=min(mn1[i-1],pr[i]-prmx[i]), 32 mn2[i]=min(mn2[i-1],pr[i]); 33 // _mn1[n]=0,_mn2[n]=af[n]; 34 for(i=n;i;i--) 35 _mn1[i]=min(_mn1[i+1],af[i]-afmx[i]), 36 _mn2[i]=min(_mn2[i+1],af[i]); 37 for(i=1;i<=n;i++) 38 //i=15,//printf(" %lld-%lld %lld-%lld ",af[i+1],_mn2[i+1],pr[i-1],mn1[i-1]), 39 ans=max(ans,(af[i+1]-_mn2[i+1])+(pr[i-1]-mn1[i-1])), 40 ans=max(ans,(pr[i-1]-mn2[i-1])+(af[i+1]-_mn1[i+1])), 41 ans=max(ans,pr[i]-mn2[i]); 42 printf("%lld ",ans); 43 }