数组的最大m子段和

给定由n个整数（可能为负）组成的序列a1、a2、a3...,an, 以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和最大。

注：有些题目要求非负数答案，当m子段最大和是负数时，取最大值为0.

思路：

二维dp,dp[i][j]表示必须以数组的第j个数结尾构成的i个子段的最大值。转移方程：dp[i][j] = max(dp[i][j-1],dp[i-1][t])，i-1<=t<j。解释：当需要第j个数加入时，构成i个子段最大和由以下两种情况的最大值中产生。1.前j-1个数已经构成i段，第j个数直接加入第i段，段数不变；2.前t个数已构成i-1段，t的范围[i-1,j)，第j个数自成一段。

原始解法

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>v(n,0);

    for(int i=0;i<n;++i){
        cin>>v[i];

    }
    vector<vector<int>>dp(m+1,vector<int>(n+1,0));

    //vector<vector<int>>dp(2,vector<int>(n+1,0));
    for(int i=1;i<=m;++i)
    {
        int MAX = 0;
        for(int j=i;j<=n-m+i;++j)
        {    
            // 之前使用j-1个数已经构成的i-1段的最大值
            // 之前使用j-1个数 已经构成i段的最大值  
            // 上面两种情况构成的子段 均必须以第j-1个数结尾
            // 构成第i段  第j个数或者自成一段 或者 加入第i段
            // 两者取最大
            MAX = max(MAX,dp[i-1][j-1]);
            dp[i][j] = max(MAX,dp[i][j-1])+v[j-1];
        }
    }
    int ans = 0;
    for(int i=1;i<=N;++i)
        ans = max(ans,dp[M][i]);

    cout<<ans<<endl;

    return 0;

}

观察发现，dp数组的更新只依赖当前行和上一行，故将dp数组行维度压缩成2，滚动更新。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>v(n,0);
    for(int i=0;i<n;++i){
        cin>>v[i];

    }

    vector<vector<int>>dp(2,vector<int>(n+1,0));
    for(int i=1,k=1;i<=m;++i,k^=1)
    {
        int MAX = 0;
        for(int j=i;j<=n-m+i;++j)
        {    
            // 之前使用j-1个数已经构成的i-1段的最大值
            // 之前使用j-1个数 已经构成i段的最大值  
            // 上面两种情况构成的子段 均必须以第j-1个数结尾
            // 构成第i段  第j个数或者自成一段 或者 加入第i段
            // 两者取最大
            //MAX = max(MAX,dp[i-1][j-1]);
            //dp[i][j] = max(MAX,dp[i][j-1])+v[j-1];
               MAX=max(MAX,dp[k^1][j-1]);     //随时更新上一行最大值
               dp[k][j]=max(dp[k][j-1],MAX)+v[j-1]; //对情况1、2的选择

        }
    }
    int ans = 0;
    //for(int i=1;i<=N;++i)
    //    ans = max(ans,dp[M][i]);
    for(int i=m;i<=n;i++)   //找到第m行的最大值，即为答案
        ans=max(ans,dp[m&1][i]);
    cout<<ans<<endl;

    return 0;

}