區(qū)間連續(xù)最大和問題

#pragma comment(linker,"/STACK:1024000000,1024000000")#ifndef _GLIBCXX_NO_ASSERT#include#endif#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include// C++#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)#define lowbit(a) a&-a#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))typedef long long LL;typedef __int64 LL64;typedef unsigned long long LLU;typedef double db;const int N=1e5+10;const int inf=0x3f3f3f3f;int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};inline LL read(){? ? int c=0,f=1;? ? char ch=getchar();? ? while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}? ? while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}? ? return c*f;}int t,n,m;int num[N];int pre,last;int start,endd;int ThisSum,Maxsum;void MaxSubsequenceSum(const int num[],int n){? ? pre=0,last=0;? ? ThisSum=0,Maxsum=num[0];? ? start=0,endd=0;? ? for(int i=0; iMaxsum){? ? ? ? ? ? Maxsum=ThisSum;? ? ? ? ? ? if(ThisSum>0){? ? ? ? ? ? ? ? start=pre;? ? ? ? ? ? ? ? endd=last;? ? ? ? ? ? }? ? ? ? ? ? else{? ? ? ? ? ? ? ? start=pre;? ? ? ? ? ? ? ? endd=pre;? ? ? ? ? ? }? ? ? ? }? ? }}int main(){? ? int tot=1;? ? t=read();? ? while(t--){? ? ? ? mem(num,0);? ? ? ? n=read();? ? ? ? for(int i=0; i1000) return -1;

}

MaxSubsequenceSum(num,n);

printf("Case %d:\n",tot++);

printf("%d %d %d\n",Maxsum,start+1,endd+1);

if(t) puts("");

}

return 0;

}