[ACM] 最大子段和

找不了回去的路

题目：
http://acm.hdu.edu.cn/showproblem.php?pid=1003

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 3178   Accepted Submission(s) : 564



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

算法暂时就不描述了
代码很长，希望能帮忙找找BUG...
总是得到WA  
（提交时 getch() 去掉了的.）

1. #include "stdio.h"
   
2. int main()
   
3. {
   
4.     long int max,in,a[3],n=0;
   
5.     int i=0,j=0,p,s,e,len;
   
6.     int as,ae,bs,be;
   
7. scanf("%ld",&n);
   
8. while(n--){
   
9.     a[0]=a[1]=a[2]=-1001;
   
10.     j++;
    
11.     scanf("%d",&len);
    
12.     if(len>0){
    
13.         scanf("%ld",&in);
    
14.         max=in;
    
15.         p=1;
    
16.         ae=be=as=bs=s=e=1;
    
17.         i=0;
    
18.         /*
    
19.          *处理开始处的零与负数
    
20.          */
    
21.         while(in<0 && p<len){
    
22. 
    
23.             if(max<in){
    
24.                 max=in;
    
25.                 s=e=p;
    
26.             }
    
27.             scanf("%ld",&in);
    
28.             bs++;
    
29.             p++;
    
30.         }
    
31.         if(p>len){goto output;}/*___BAD___BAD___*/
    
32. 
    
33.         a[0]=in;
    
34.         as=ae=p;
    
35.         if(p>=len)goto output;
    
36.         scanf("%ld",&in);
    
37.         p++;
    
38.         while(in>=0 && p<=len){
    
39.             a[0]+=in;
    
40.             ae=p;
    
41.             if(p>=len)goto output;
    
42.             scanf("%ld",&in);
    
43.             p++;
    
44.         }
    
45.         if(a[0]>max){
    
46.             max=a[0];
    
47.             s=as;e=ae;
    
48.         }
    
49.         a[1]=in;i=1;
    
50. 
    
51. 
    
52. 
    
53. 
    
54.         while(1){
    
55.             if(p>=len)goto output;
    
56.             scanf("%ld",&in);
    
57.             p++;
    
58.             switch(i){
    
59.                 case 1:
    
60.                     if(in<0){
    
61.                         a[1]+=in;   
    
62.                     }
    
63.                     else{
    
64.                         a[2]=in;i=2;bs=be=p;/*调整a[2]的位置*/
    
65.                     }break;
    
66.                 case 2:
    
67.                     if(in>=0){
    
68.                         a[2]+=in;
    
69.                         be=p;
    
70.                     }
    
71.                     else{
    
72.                         
    
73.                         /*调整max*/
    
74.                         if(max<a[0]){
    
75.                             max=a[0];s=as;e=ae;
    
76.                         }
    
77.                         if(max<a[0]+a[1]+a[2]){
    
78.                             max=a[0]+a[1]+a[2];
    
79.                             s=as;e=be;
    
80.                         }
    
81.                         if(max<a[2]){
    
82.                             max=a[2];
    
83.                             s=bs;e=be;
    
84.                         }
    
85. 
    
86.                         /*调整下一个a[0]*/
    
87.                         if(a[0]+a[1]>0){
    
88.                             a[0]=a[0]+a[1]+a[2];
    
89.                             ae=be;/*下一个a[0]*/
    
90.                         }else{
    
91.                             a[0]=a[2];
    
92.                             as=bs;ae=be;
    
93.                         }
    
94.                         i=1;
    
95.                         a[1]=in;
    
96.                     }break;
    
97.             }/*End of switch*/
    
98.         }
    
99.     }/*End of one case's deal.*/
    
100. 
     
101. 
     
102. output:
     
103.     if(max<a[0]){
     
104.         max=a[0];
     
105.         e=ae;s=as;
     
106.     }
     
107.     if(max<a[0]+a[1]+a[2]){
     
108.         max=a[0]+a[1]+a[2];
     
109.         s=as;e=be;
     
110.     }
     
111.     if(max<a[2]){
     
112.         max=a[2];
     
113.         s=bs;e=be;
     
114.     }
     
115. 
     
116.     printf("Case %d:\n%ld %d %d\n",j,max,s,e);
     
117.     if(n!=0)printf("\n");
     
118. }/*End of n's loop*/
     
119. getch();
     
120. 
     
121. return 0;
     
122. }

复制代码

[ 本帖最后由 找不了回去的路 于 2007-1-23 18:15 编辑 ]

wshong

其实楼上可以用动态规划解

小I

其实就是动态规划...