```   1 //533278 2008-03-30 19:03:17 Accepted 1003 31MS 264K 1206 B C++ whiteTiger 非DP方法
2 #include <stdio.h>
3
4 int main(){
5     int CaseNum;
6     scanf("%d", &CaseNum);
7     int a[100000];
8     for(int Case = 0; Case < CaseNum; Case++){
9         int num;
10         scanf("%d",&num);
11         for(int i = 0; i < num; i++){
12             scanf("%d", &a[i]);
13         }
14         int currentSum, maxSum, start, end;
15         //最大子段和
16         start = 0;
17         end = 0;
18         maxSum = -1001;     //记录最大值，n范围-1000-1000
19         currentSum = 0;     //记录当前总和
20         for(int i= 0; i < num; i++){
21             for(int j = i; j  < num; j++){
22                 currentSum += a[j];
23                 if(currentSum > maxSum){
24                     maxSum = currentSum;
25                     start = i+1;
26                     end = j+1;
27                 }
28                 if(currentSum < 0){
29                     i = j;
30                     currentSum = 0;
31                     break;
32                 }
33             }
34             currentSum = 0;
35         }
36         printf("Case %d:\n", Case+1);
37         printf("%d %d %d\n", maxSum, start, end);
38         if(Case != CaseNum -1){
39             printf("\n");
40         }
41     }
42     return 0;
43 }
```

```   1 //ASUN 我们的数据结构书上有介绍，我选了算法复杂度最小的一种算法，O(N)
2
3 #include"stdio.h"
4
5 void main()
6 {
7         int dig;
8         int n,k,t,count;
9         int Newi,ThisSum;
10         int MaxDig,Maxi,Maxj,MaxDi,MaxSum;
11         scanf("%d",&k);
12
13         for(count=0;count<k;count++)
14         {
15                 scanf("%d",&n);
16
17                 ThisSum=MaxSum=Maxi=Maxj=MaxDi=Newi=0;
18                 for(t=0;t<n;t++)
19                 {
20                         scanf("%d",&dig);
21                         if(t==0)
22                                 MaxDig=dig;
23
24                         ThisSum+=dig;
25                         if(MaxDig<dig)
26                         {
27                                 MaxDig=dig;
28                                 MaxDi=t;
29                         }
30
31                         if(ThisSum>MaxSum)
32                         {
33                                 MaxSum=ThisSum;
34                                 Maxi=Newi;
35                                 Maxj=t;
36                         }
37                         else if(ThisSum<0)
38                         {
39                                 ThisSum=0;
40                                 Newi=t+1;
41                         }
42                 }
43
44                 if(MaxSum==0)
45                 {
46                         MaxSum=MaxDig;
47                         Maxi=Maxj=MaxDi;
48                 }
49
50                 printf("Case %d:\n%d %d %d\n",count+1,MaxSum,Maxi+1,Maxj+1);
51                 if(count!=k-1)
52                         printf("\n");
53         }
54 }
```

hdu1003 参考答案 (last edited 2008-11-09 15:34:06 by 218)

ch3n2k.com | Copyright (c) 2004-2022 czk.