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 阅读(274) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案(6)

搜索

最新评论

阅读排行榜

评论排行榜