HDOJ 1024 Max Sum Plus Plus

/*超时。题意：输出m个子序列和的最大值思路：动态规划 + 滑动数组d[m][j] = max(d[m][j - 1] + e[j], max(d[m - 1][k] + e[j]) | k ∈ [m -1, j)).表示前j个序列分割成m组，最大序列和因为状态方程中只用到d[m]和d[m - 1]两个状态，所以只需要一个二维数组即可。优化：至于max(d[m - 1][k] + e[j])过程，可以直接在d[0][j]中存储在j之间分割成m - 1的最大值。这样状态转移方程变为d[1][j] = max(d[1][j - 1] + e[j], d[0][j - 1] + e[j]);*/#include <iostream>using namespace std;const int nMax = 1000010;const int MIN = -0x7fffffff;int e[nMax];__int64 d[2][nMax];int m, n;int main(){    //freopen("e://data.txt", "r", stdin);    while(scanf("%d%d", &m, &n) != EOF)    {        for(int i = 1; i <= n; ++ i)            scanf("%d", &e[i]);        memset(d, 0, sizeof(d));        for(int i = 1; i <= m; ++ i)        {            for(int j = i; j <= n; j ++)            {                /*                for(int k = m - 1; k < j; k ++)                {                    d[1][j] = max(d[0][k] + e[j], d[1][j]);                }                */                d[1][j] = max(d[0][j - 1] + e[j], d[1][j]);                d[1][j] = max(d[1][j - 1] + e[j], d[1][j]);//临界时候已经被包含在内，所以不需要再另外做处理。            }            for(int j = i; j <= n; ++ j)            {                d[0][j] = max(d[0][j - 1], d[1][j]);                d[1][j] = MIN;            }        }        /*        int _max = 0;        for(int i = m; i <= n; ++ i)            _max = max(_max, d[0][i]);            */        printf("%I64d\n", d[0][n]);    }    return 0;}