最大子段和

 

N个整数组成的序列a11,a22,a33,…,ann， 求该序列如aii+ai+1i+1+…+ajj的连续子段和的最大值。当所给的整数均为负数时和为0。

例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

Input

第1行：整数序列的长度N（2 <= N <= 50000) 
第2 - N + 1行：N个整数（-10^9 <= Aii <= 10^9）

Output

输出最大子段和。

Sample Input

6
-2
11
-4
13
-5
-2

Sample Output

20

思路其实很简单，自己拿笔照着程序模拟一下就会很明白。

//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long LL;
const int MAXN = 50000+10;
LL dp[MAXN];
LL num[MAXN];

int main()
{
    int n;
    while( scanf("%d", &n) != EOF )
    {
        memset(dp, 0, sizeof(dp));
        bool flag = false;
        for( int i=1; i<=n; i++ )
        {
            scanf("%lld", &num[i]);
            if( num[i] > 0 )
                flag = true;
        }
        if( !flag )
            printf("%d\n", 0);
        else
        {
            LL temp = 0;
            //LL dp = 0;
            for( int i=1; i<=n; i++ )
            {
                if( temp > 0 )
                    temp += num[i];
                else
                    temp = num[i];
                //if( temp > dp[i] )
                //    dp[i] = temp;
                dp[i] = max(dp[i-1], temp);
            }
            printf("%lld\n", dp[n]);
        }
    }

    return 0;
}