[P1121]环状最大两段子段和

Luogu1121

给定一个环状序列((a_1)和(a_n)相邻)，求：连续不重叠且非空的两段使得这两段和最大

有两种情况：中间选两段或者用到环的左右部分，
一种思路是用线段树维护普通的最大子段和(而且要在中间)，再加上环的左右两段；中间的两段可以把所有数负过来，就变成了求中间加左右的最小值，(ans2=sum+query())
但是这样会有bug : 如果(T.Max[1]==T.L[1])就无法处理了．

所以不能用线段树，这里用到DP：枚举以(i)为界，求左边最大值+右边最大值即可

还要特判：如果正数(<=1)个，则直接选出最大的两个数．

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>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
",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
",max(ans1,ans2));
}