HDU1024 Max Sum Plus Plus 动态规划

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 1000005
using namespace std;

int M, N, seq[MAXN];

int pre[MAXN], cur[MAXN];

int DP()
{
    int Max;
    memset(pre, 0, sizeof (pre));
    memset(cur, 0, sizeof (cur));
    for (int i = 1; i <= M; ++i) { 
        Max = 0x7fffffff+1;
        for (int j = i; j <= N; ++j) {
            cur[j] = max(cur[j-1], pre[j-1]) + seq[j];
            pre[j-1] = Max;   // pre 并不是保留到第j为截止（保留第j个数）的最优值 
            Max = max(Max, cur[j]);
        } 
    }
    return Max;
}

int main()
{
    while (scanf("%d %d", &M, &N) != EOF) {
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &seq[i]);
        }
        printf("%d\n", DP());
    }
    return 0;
}