最大子段和

Description

给出n个整数序列（可能为负数）组成的序列a₁, a₂, ..., a_n，求该序列形如的子段和的最大值。当所有整数均为负数时，定义最大子段和为0。

Input

多测试用例。每个测试用例占2行：

第一行是序列的个数n（0 < n ≤ 10000），第二行是n个整数。

Output

为每个测试用例输出一行结果：最大子段和。

Sample Input

6
-2 11 -4 13 -5 -2
3
1 2 3

Sample Output

20
6

AC代码：

#include<stdio.h>
int a[10001],b[10001];
int main( )
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int maxx=-1;
        for(int i=1 ; i<=n ; i++)
        scanf("%d",&a[i]);
        for(int i=1 ; i<=n ; i++)
        {
            if(b[i-1]>0)
                b[i]=b[i-1]+a[i];
            else
                b[i]=a[i];
            if(b[i]>maxx)
                maxx=b[i];
        }
        printf("%d
",maxx);
    }
}