杭电OJ 1024（C++）_杭电oj1024

这一题花了很长时间，补了动态规划的知识，参考了几篇博客。

https://www.cnblogs.com/dongsheng/archive/2013/05/28/3104629.html

https://blog.csdn.net/aaaliaosha/article/details/77163512

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010;
 
int m, n;
int num[N]; //长度超过一百万的数组不能定义在函数内部，否则造成栈溢出
int dp[N]; //dp[j]存储以num[j]结尾的前j个数中，分成i段的最大值
int pre[N]; //pre[j]存储前j个数中（不一定以num[j]结尾），分成i段的最大值
 
int max(int a, int b)
{
	return a > b ? a : b;
}
 
int main()
{
	while (cin >> m >> n)
	{
		for (int i = 1; i <= n; i++) //读入数据
			cin >> num[i];
 
		num[0] = 0;
		memset(dp, 0, sizeof(dp)); //初始化数组dp
		memset(pre, 0, sizeof(pre)); //初始化数组pre
 
		int Sum;
		for (int i = 1; i <= m; i++) //自底向上动态规划，规模大的解完全依赖于规模小的解
		{
			Sum = -9999999;
			for (int j = i; j <= n; j++)
			{
				dp[j] = max(dp[j - 1], pre[j - 1]) + num[j];
				pre[j - 1] = Sum;
				Sum = max(Sum, dp[j]);
			}
		}
		cout << Sum << endl;
	}
 
	return 0;
}