分治写法。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=100010; int T,n,a[maxn],L,R,ans; void check(int l,int r,int s) { if(s<ans) return; if(s>ans) { L=l, R=r, ans=s; return ;} if(l<L) L=l, R=r, ans=s; else if(l==L&&r<R) L=l, R=r, ans=s; } int get(int l,int r) { if(l==r) { check(l,r,a[l]); return a[l]; } int m=(l+r)/2; int x1=get(l,m),x2=get(m+1,r); int sum1=0,f1=-2000,posl; for(int i=m;i>=l;i--) sum1=sum1+a[i],f1=max(f1,sum1); sum1=0; for(int i=m;i>=l;i--) { sum1=sum1+a[i]; if(sum1==f1) posl=i; } int sum2=0,f2=-2000,posr; for(int i=m+1;i<=r;i++) sum2=sum2+a[i],f2=max(f2,sum2); sum2=0; for(int i=m+1;i<=r;i++) { sum2=sum2+a[i]; if(sum2==f2) {posr=i;break;} } check(posl,posr,f1+f2); return max(x1,max(x2,f1+f2)); } int main() { scanf("%d",&T); int cas=1; while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ans=-2000,L=n+1,R=n+1; get(1,n); printf("Case %d: ",cas++); printf("%d %d %d ",ans,L,R); if(T) printf(" "); } return 0; }