Max Sum(hd P1003)

时间：2015-05-10 06:16:58 阅读：283 评论：0 收藏：0 [点我收藏+]

Problem Description

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input

2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5

Sample Output

Case 1: 14 1 4 Case 2: 7 1 6

超时代码

#include<stdio.h>
int main()
{
   int a[100000],T,N,T1,j,i;
   scanf("%d",&T);
   T1=T;
   while(T--)
   {
       int Msum=0,sum=0,s=0,w=0;
       printf("case %d:\n",T1-T);
       scanf("%d",&N);
       for(i=0;i<N;i++)
           scanf("%d",&a[i]);
       Msum=a[0];
       for(j=0;j<N;j++)
       {
           for(i=j;i<N;i++)
           {
               if(a[i]<=0)
               {
                   sum+=a[i];
                   continue;
               }
               sum+=a[i];
               if(Msum<sum)
               {
                   s=j;
                   w=i;
                   Msum=sum;
               }
           }
           sum=0;
       }
       printf("%d %d %d\n\n",Msum,s+1,w+1);
   }
   return 0;
}

AC代码

 1 /*状态转移方程 d[i] = max(d[i-1]+a[i], a[i])
 2 　　d[i]表示以i位置结束的最大子序列之和。*/
 3 #include<stdio.h>
 4 int main()
 5 {
 6     int a[100000];
 7     int T,T1;
 8     scanf("%d",&T);
 9     T1=T;
10     while(T--)
11     {
12         int  sum=0,msum=0,i,x=0,y=0,start=0,end=0,N;
13         scanf("%d",&N);
14         for(i=0;i<N;i++)
15             scanf("%d",&a[i]);
16         sum=a[0];
17         msum=sum;
18         for(i=1;i<N;i++)
19         {
20             if(sum<0)/*dp[i-1]对a[i]不仅没有贡献，反而有损害，就应该舍弃*/
21             {
22                 x=y=i;
23                 sum=a[i];
24             }
25             else
26             {
27                 sum+=a[i];
28                 y=i;
29             }
30             if(sum>msum)
31             {
32                 msum=sum;
33                 start=x;
34                 end=y;
35             }        
36         }
37         printf("Case %d:\n",T1-T);
38     
39         if(T==0)
40         printf("%d %d %d\n",msum,start+1,end+1);
41         else
42         printf("%d %d %d\n\n",msum,start+1,end+1);
43         
44     }
45 }

Max Sum(hd P1003)

原文：http://www.cnblogs.com/a1225234/p/4491605.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)