51nod 1049 最大子段和（基礎dp）

假設sum[i]表示以第i個數字為結尾的最大子段和，則sum[i]=max(sum[i-1]+A[i],A[i])，因為子段是連續的。。由狀态轉移方程可以知道，隻有在sum[i-1]<0的情況下,sum[i]=A[i]，否則，sum[i]=sum[i-1]+A[i],是以可以邊輸入邊處理，一層循環搞定

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = ;
ll A[MAXN];
ll sum[MAXN];

int main()
{
    //freopen("in","r",stdin);
    int n;
    ll res;
    scanf("%d",&n);
    memset(sum,,sizeof(sum));
    for(int i = ; i <= n; ++i)
        scanf("%lld",&A[i]);
    res = ;
    for(int i = ; i <= n; ++i)
    {
        sum[i] = max(sum[i-]+A[i],A[i]);
        if(sum[i] > res)
            res = sum[i];
    }
    printf("%lld\n",res);
    return ;
}