首页 > 代码库 > 杭电1003

杭电1003

 1 #include<stdio.h>
 2 
 3 int a[100005],dp[100005];
 4 
 5 int main()
 6 {
 7     int n,m,i,maxn,xx,yy,x,y,t;
 8     while(~scanf("%d",&n))
 9     {
10         for(t=0; t<n; ++t)
11         {
12             scanf("%d",&m);
13             for(i=0; i<m; ++i)
14                 scanf("%d",&a[i]);
15             x=y=xx=yy=0;
16             maxn=dp[0]=a[0];
17             for(i=1; i<m; ++i)
18             {
19                 if(dp[i-1]+a[i]<a[i])
20                 {
21                     dp[i]=a[i];
22                     xx=i;
23                     yy=i;
24                 }
25                 else
26                 {
27                     dp[i]=dp[i-1]+a[i];
28                     yy=i;
29                 }
30                 if(dp[i]>maxn)
31                 {
32                     maxn=dp[i];
33                     x=xx;
34                     y=yy;
35                 }
36             }
37             if(t)
38                 printf("\n");
39             printf("Case %d:\n",t+1);
40             printf("%d %d %d\n",maxn,x+1,y+1);
41         }
42     }
43 }

 

杭电1003