kuangbin 专题十二： 基础DP1 Max Sum Plus Plus

题目链接：
传送门

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int m, n, mx, a[N], dp[N], g[N];
int main() {
	while(scanf("%d%d",&m, &n)!=EOF) {
		//输入数据
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		//初始化数组
		memset(dp, 0, sizeof(dp));
		memset(g, 0, sizeof(g));
		//枚举选择字段的数量
		for(int i = 1; i <= m; i++) {
			mx = -0x3f3f3f3f;
			//枚举前j段的最优解
			for(int j = i; j <= n; j++) {
				dp[j] = max(dp[j - 1], g[j - 1])+ a[j];
				//存下前i - 1个数中只拿j - 1份物品的最优解
				g[j - 1] = mx;
				//更新获取本轮结果中的最优解
				mx = max(mx, dp[j]);
			}
		}
		//输出结果
		printf("%d\n", mx);
	}
	return 0;
}

这道题可以用动态规划来做
首先分析一下基本情况，该问题可以从n，m入手进行划分，设i，j两个变量用来分别表示前n个数和前m个选取方案。即分别枚举1，2，3，4，5……个数字的情况下，取子段1个，2个，3个……的情况，根据这个分析，我们很明显就能构思到一个二重循环的结构了，那接下来细节要怎么实现
首先最简单的就是开一个二维dp数组然后枚举上述讲的情况，找到了拆分集合，现在我们就要思考状态的转移方程是什么。其实这道题有两个状态dp[i][j - 1] + a[j] 和 max(dp[i - 1][k] + a[i])。前者表示在取了j个子段后再把i拿上合并到第j组字段中去，而第二个式子则是指拿了j - 1一个字段后，拿上当前第i个数字作为第j个子段。
大致思路清楚了记下来就是优化了，因为我们如果开个二维数组消耗会很大，因此我们可以把这个数组优化为一维，我们只需要记录i - 1个数字时的最优取法，和当前取法往右合并两种状态即可，因此，我们们可以开个数组，分别表示i - 1时每个状态的最大值，转移方程就会变为**dp[j] = max(dp[j - 1], g[j - 1])+ a[j]**具体每次的更新操作，可以看看代码及注释。