http://pat.zju.edu.cn/contests/pat-practise/1007
老的不能再老的问题
1 #include <stdio.h> 2 int K; 3 int num[10003]; 4 int sum[10003]; 5 int max_sum; 6 int main() 7 { 8 bool all_negative=true; 9 int start=0,end=0,cur_start=0,cur_end=0; 10 scanf("%d",&K); 11 int i; 12 for(i=0;i<K;i++) { 13 scanf("%d",&num[i]); 14 if(num[i]>=0){ 15 all_negative=false; 16 } 17 } 18 if(all_negative) { 19 printf("0 %d %d\n",num[0],num[K-1]); 20 return 0; 21 } 22 max_sum=num[0]; 23 sum[0]=num[0]; 24 for(i=1;i<K;i++) { 25 if(sum[i-1]>0) { 26 sum[i]=sum[i-1]+num[i]; 27 cur_end=i; 28 if(sum[i]>max_sum) { 29 start=cur_start; 30 end=cur_end; 31 max_sum=sum[i]; 32 } 33 } else { 34 //如果之前的最大和小于零，则另起炉灶了 35 sum[i]=num[i]; 36 cur_start=cur_end=i; 37 if(sum[i]>max_sum) { 38 start=end=i; 39 max_sum=sum[i]; 40 } 41 } 42 } 43 printf("%d %d %d\n",max_sum,num[start],num[end]); 44 }