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 }