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
Sample Output
40
Source
1
#include <cstdio>
2//#include <fstream>
3using namespace std;
4int a[100002],b[100002],c[100002];
5
int main()
{
6
7
/**//* fstream fin("2593.txt");
8 if(!fin){
9 cout<<"can not open the file "<<endl;
10 system("pause");
11 return 0;
12
}*/
13 int n;
14 int max;
15 int tmp=0,sum=0;
16 scanf("%d",&n);
17
18 while(n){
19 for(int i=0;i<n;i++){
20 scanf("%d",&a[i]);
21 b[i]=c[i]=0;
22 }
23
24 tmp=0;
25 sum=-1000000;
26 for(int j=0;j<n;j++){
27 if(tmp>0)tmp+=a[j];
28 else {
29 tmp=a[j];
30 }
31 if(tmp>sum){
32 sum=tmp;
33 }
34 b[j]=sum;
35 }
36 tmp=0;
37 sum=-1000000;
38 for(int j=n-1;j>=0;j--){
39 if(tmp>0)tmp+=a[j];
40 else {
41 tmp=a[j];
42 }
43 if(tmp>sum){
44 sum=tmp;
45 }
46 c[j]=sum;
47 }
48 max=-11000000;
49 for(int j=0;j<n-1;j++){
50 if(b[j]+c[j+1]>max){
51 max=b[j]+c[j+1];
52 //cout<<"bj"<<b[j]<<" ";
53 //cout<<"c[j+1]"<<c[j+1]<<endl;
54 }
55 }
56 printf("%d",max);
57 //system("pause");
58 scanf("%d",&n);
59 }
60 //fin.close();
61 return 0;
62
}
63
64
65
66
67