题目大意：
给定一个长度为\(n\)数组，求划分成\(m\)段不相交区间的子段和最大值得问题
那么需要考虑得就是对于第i个数字，是否选中它在m个区间中，以及如果选中它那么它在第几个区间中
定义\(dp[i][j]\)是前\(j\)个数字，选中第\(j\)个数字，划分出\(i\)个不相交区间的最大和
决策：第\(j\)个数字划分到第\(i\)个区间，还是开辟一个新的区间
状态转移：\(dp[i][j]=max\){ \(dp[i][j-1]+a[j], max\){ \(dp[i-1][k]\) | \(0<k<j\) }\(+a[j]\) }
\(Complexity:O(m\times n^2)\)需要优化
利用滚动数组优化，只需要一维的\(dp[j]\)
用一个数组\(maxi[j-1]\)记录\(dp[i-1][k]\)
\(Conplexity:O(m\times n)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int INF=0x7fffff;
//------------------------
int a[MAXN], maxii, dp[MAXN], maxi[MAXN];
int main(void)
{
int m, n;
while(scanf("%d%d", &m, &n)!=EOF){
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
maxi[i]=0; //maxi[0], maxi[1], ..., maxi[n-1]，每次都是用完maxi[j-1](i-1)后才更新成maxi[j-1](i)，所以在i=1时需要先全部初始化为0
}
maxi[0]=0; //同上面初始化为0
dp[0]=0; //dp[1]依赖dp[1-1]=dp[0]，所以要初始化为0，之后dp[2]依赖dp[1]，dp[3]依赖dp[2],...,所以只需要初始化dp[0]=0即可
for(int i=1; i<=m; i++){
maxii=-INF;
for(int j=i; j<=n; j++){
dp[j]=max(dp[j-1]+a[j], maxi[j-1]+a[j]);
maxi[j-1]=maxii; //用完maxi[j-1](i-1)就更新maxi[j-1]为j-1(i)的maxii
maxii=max(dp[j], maxii);
}
}
printf("%d\n", maxii);
}
return 0;
}