Max Sequence(双向DP) -- 编程驿站-- 编程爱好者博客

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;
}

博客介绍

正文

Max Sequence(双向DP)2007-08-13 17:22:00

评论