Max Sum Plus Plus_牛客博客

参考：HDU 1024 Max Sum Plus Plus（动态规划，给定一个数组，求其分成m个不相交子段和最大值的问题）

思路：想了好久好久...才把它想懂。但是还是不明白为什么最初的代码会WA

用dp来写这道题，最原始的公式为dp[i][j]=max(dp[i][j-1]+max(dp[i-1][t](i-1<=t<=j-1)))+s[j]，但是要考虑到n的范围会很大，开不了\(n^2\)的二维数组，但是通过观察可以发现，我们只需要知道上一层的dp的值即可，即当i-1时的dp的各个位置上的值
dp[maxn]：保存当前层的前一个值
Max[maxn]：保存上一层当前位置对应的最大值

代码：

// Created by CAD on 2019/10/16.
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int maxn=1e6+5;
int s[maxn];
int dp[maxn],Max[maxn];
int main()
{
    int n,m;
    while(~scanf("%d%d",&m,&n))
    {
        for(int i=1;i<=n;++i)
            scanf("%d",&s[i]),dp[i]=Max[i]=0;
        dp[0]=Max[0]=0;
        int temp;
        for(int i=1;i<=m;++i)
        {
            temp=-inf;
            for(int j=i;j<=n;++j)
            {
                dp[j]=max(dp[j-1],Max[j-1])+s[j];
                Max[j-1]=temp;
                temp=max(temp,dp[j]);
            }
        }
        cout<<temp<<endl;
    }
    return 0;
}

有空的时候再想想为啥这么写会错：

for(int i=1;i<=m;++i)
{
    for(int j=i;j<=n;++j)
    {
        dp[j]=max(dp[j-1],Max[j-1])+s[j];
        Max[j-1]=max(Max[j-2],dp[j-1]);
    }
    Max[n]=max(Max[n-1],dp[n]);
}
cout<<Max[n]<<endl;