## POJ 2593 Max Sequence

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];
5int 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

posted on 2010-06-16 11:10 bluedream 阅读(152) 评论(0)  编辑 收藏 引用

 < 2020年3月 >
23242526272829
1234567
891011121314
15161718192021
22232425262728
2930311234

• 随笔 - 6
• 文章 - 0
• 评论 - 0
• 引用 - 0

•