HDU - 1024 Max Sum Plus Plus（区间dp）

区间dp

题意：在n个数里选出连续的m组数使其和最大

思路：dp[i][j], 表示分i个组时前j个数的最大值

所以有递推方程dp[i][j] = max(dp[i - 1][k] + w[j], dp[i][j-1] + w[j]);

其中k取1.2.3…j - 1;把第j个数当做新的一组或当做上一个组的长度加一取最大，因为考虑到时间是n^3的关系，所以再对方程进行优化

因为dp[i - 1][k]为i - 1组的前j - 1 个数的最大值，所以可以直接将上一组的前k个最大值记下后不断更新，在这里记进了maxl数组；

二维数组前j个数的最大值就失去了意义，可以直接转化为一维， dp[j] 为前j个数组合后的最大值（一定会有第j个数）

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int dp[1000005];
int ch[1000005];
int maxl[1000005];
const int INF = 0x7fffffff;
int main()
{
    int n, m;
    int mmax;
    while(cin >> n >> m)
    {
        memset(dp, 0, sizeof(dp));
        memset(maxl, 0, sizeof(maxl));
        memset(ch, 0, sizeof(ch));

        for(int i = 1; i <= m; i++)
        {
            scanf("%d", &ch[i]);
        }
        for(int i = 1; i <= n; i++)
        {
            mmax = -INF;//因为有负数，所以初始为负无穷
            for(int j = i; j <= m; j++)
            {
                dp[j] = max(dp[j - 1] + ch[j], maxl[j - 1] + ch[j]);//这里用的是上一组的maxl的最大值
                maxl[j - 1] = mmax;//更新最大值为本组1到j - 1为止的最大值 因为mmax还未更新， 为j - 1 的最大值
                mmax = max(mmax, dp[j]);//更新最大值为到j的最大值
            }
        }
        printf("%d\n", mmax);
    }
    return 0;
}