Max Sequence  Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB Total submit users: 88, Accepted users: 73 Problem 10478 : No special judgement Problem description Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N). You should output S. Input The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0. Output For each test of the input, print a line containing S. Sample Input 5 -5 9 -5 11 20 0 #include <stdio.h> #include <limits.h> int a[100002],b[100002],c[100002]; int main(){     int i,n,t,sum;     while(scanf("%d",&n) && n){         for(i=0; i<n; i++)             scanf("%d",&a[i]);         for(t=0,sum=INT_MIN,i=0; i<n; i++){             if(t>0)                 t+=a[i];             else                  t=a[i];             if(t>sum)                 sum=b[i]=t;             else                 b[i] = sum;         }         for(t=0,sum=INT_MIN,i=n-1; i>=1; i--){             if(t>0)                 t+=a[i];             else                  t=a[i];             if(t>sum)                 sum=c[i]=t;             else                 c[i] = sum;         }         for(sum=b[0]+c[1],i=2; i<n-2; i++){             if(b[i]+c[i+1]>sum)                 sum=b[i]+c[i+1];         }         printf("%d\n",sum);     }     return 0; }

评论