给定一个环状序列(\(a_1\)和\(a_n\)相邻)，求：连续不重叠且非空的两段使得这两段和最大
有两种情况：中间选两段或者用到环的左右部分，
一种思路是用线段树维护普通的最大子段和(而且要在中间)，再加上环的左右两段；中间的两段可以把所有数负过来，就变成了求中间加左右的最小值，\(ans2=sum+query()\) 但是这样会有bug : 如果\(T.Max[1]==T.L[1]\)就无法处理了．所以不能用线段树，这里用到DP：枚举以\(i\)为界，求左边最大值+右边最大值即可
还要特判：如果正数\(<=1\)个，则直接选出最大的两个数．
#include#include #include #include #define debug(...) fprintf(stderr,__VA_ARGS__)#define Debug(x) cout<<#x<<"="< < 57){if(c=='-')f=-1;c=getchar();} while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar(); return f*x;}const int N=2e5+5;int a[N],l[N],r[N];int n,sum,cnt,ans1,ans2;inline int query(){ // 中间两段最大 int res=-INF; memset(l,0xcf,sizeof l); memset(r,0xcf,sizeof r); for(int i=1;i<=n;i++) l[i]=max(l[i-1],0)+a[i]; for(int i=1;i<=n;i++) l[i]=max(l[i-1],l[i]); for(int i=n;i>=1;i--) r[i]=max(r[i+1],0)+a[i]; for(int i=n;i>=1;i--) r[i]=max(r[i+1],r[i]); for(int i=1;i<=n-1;i++) res=max(res,l[i]+r[i+1]);//以i为界,左边最大值+右边最大值 return res;}int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i],cnt+=(a[i]>0); if(cnt<=1){ sort(a+1,a+n+1); printf("%d\n",a[n]+a[n-1]); return 0; } ans1=query(); for(int i=1;i<=n;i++) a[i]=-a[i]; ans2=sum+query(); printf("%d\n",max(ans1,ans2));}