HDU1024 Max Sum Plus Plus

题意：给你一个N个元素的数列，你需要从中选M个区间，区间之间不能有交叉，问选取的M个区间之和最大值是多少？ (N是1e6的数量级)

分析

我们考虑一个数一个数的放，过程是怎么样的。如果当前是选取第i个区间，现在要尝试放入a[j]，那么就会出现两种情况：
1.a[j]直接跟在第i个区间的后面，最开始相当于跟在空区间的后面，后来就是a[j+1]跟在a[j]的后面组成区间
2.找到j之前选择i-1个区间的最优值+新开一个区间[j,j].

假如现在是第i轮区间选择:

dp[j]: 当前轮第j个位置的两种选择情况的最大值
mx:实时保存本轮在第j个位置选择后的最优值，当前轮的最优值
best[j-1]:上一轮在区间[1,j-1]选取i-1个区间的最优值，best[]是一个滚动数组，保存当前轮的最优值在下一轮使用

遇到的问题

找到j之前选择i-1个区间的最优值应该怎么处理呢？
当我们进行一轮新区间的时候，我们要使用到上一轮的j之前的最优值，同时又要保存j之前选取新区间之后的最优值
第一轮区间选择，其j之前的最优值都是0，因为只选取了0个区间
当我们用了上一轮的best[j-1]，紧接着就要更新下一轮的best[j-1]，此处具体看代码

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6+100;
typedef long long ll;
int M,N;
int arr[maxn];//原数组
ll best[maxn],dp[maxn];//best上一轮的最优值，本轮dp[j]:本轮选择了j位置的最优值
int main(){
    while(~scanf("%d %d",&M,&N)){
        memset(best,0,sizeof(ll)*N+10);
        memset(dp,0,sizeof(ll)*N+10);
        ll mx;
        for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
        for(int i = 1;i<=M;i++){//轮次
            mx = -1e18;
            for(int j = i;j<=N;j++){
                dp[j] = max(dp[j-1],best[j-1])+arr[j];//选择j位置后的最优值,使用掉上一轮best[j-1]
                best[j-1] = mx;//保存本轮的j-1的最优值，放在下一轮用
                mx = max(mx,dp[j]);//更新本轮j位置的最优值
            }
        }
        printf("%lld\n",mx);
    }

    return 0;
}