hdu 1003

区间连续最大和问题

#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;

}