题目链接
题目大意：给$n$个数，把他们划成$m$个连续子段，求这个$m$个连续子段的和的最大值。子段与子段之间不交叉，可以不连续。
??这题如果直接做的话不太好做，我们先考虑一下$m=1$的情况。设$dp$数组为$dp[i][j]$，$i$表示划成$i$段的最大子段和，$j$表示当前第$j$个元素，数组$a$存的是$m$个元素的值。
??1.$m=1$时，就相当于最经典的连续子段和问题了，状态转移方程就是$dp[1][j] = max(a[j], dp[1][j-1]+a[j])$。
??2.$m=2$时，假设我们从$1$到$j(j\in [2,n])$之间选两个连续子段的话，分两种情况，假设选择的最左边的子段为蓝色，中间的为黄色，当前数组的元素为红色。
??(1)当我们选的当前元素为独立一段时：
??
。
??我们只要选一个在$j$之前的一个最大子段和再加上当前元素即可。$j$之前的一个最大子段和我们遍历之前求出的$m=1$的时候最大子段和就能求出来。
??(2)当我们之前已经选好了两段，当前的元素与第二段相连时(比如说发生上一种情况之后的下一个元素)：
??
。
??这时候相当于在之前已经选好的最大值的基础上加上当前元素的值。
??(3)所以说，$m=2$时的状态转移方程为$dp[2][j] = max(dp[2][j-1], pre(1, j-1)) + a[j]$，$pre()\(用来求出\)[1,j-1]$之间的最大子段和。
??3.$m=3$时, 与$m=2$时的情况类似，我们可以把它拆成已经选好了$2$个子段，求第$3$个子段的情况。
??4.从上面的过程中我们可以总结出来状态转移方程为$dp[i][j] = max(dp[i][j-1], pre(i-1, j-1)) + a[j], \ pre(i-1, j-1) = max(dp[i-1][k])(k\in [i-1, j-1])$
const int maxn = 1e6+10;
int n, m;
ll dp[10][maxn], arr[maxn];
ll pre(int floor, int r) {
ll maxx = -LLONG_MAX;
for (int i = floor; i<=r; ++i)
maxx = max(maxx, dp[floor][i]);
return maxx;
}
int main(void) {
while(~scanf("%d%d", &n, &m) && m) {
for (int i = 1; i<=m; ++i) scanf("%lld", &arr[i]);
ll ans = -LLONG_MAX;
for (int i = 1; i<=n; ++i)
for (int j = i; j<=m; ++j) {
dp[i][j] = max(dp[i][j-1], pre(i-1, j-1)) + arr[j];
ans = max(ans, dp[i][j]);
}
printf("%lld\n", ans);
}
return 0;
}
??然后你就TLE了(笑)
??所以说我们还需要对时间进行优化，好像空间也得优化一下不然可能会MLE。
??首先对时间进行优化，我们可以很容易发现我们的时间复杂度是$O(mn^2)$的，但是如果我们优化一下求$pre$的话就能把时间复杂度缩小到$O(mn)$, 我们只需要用一个数组，将上一组元素的每个元素之前最大的元素保存下来就行了。
??然后就是对空间优化，很明显$dp[i]$的值之和$dp[i-1]$有关，所以我们没有必要开一个二维数组，只用一维数组就行了，这种优化背包问题之类的$dp$问题已经讲的很多了就不多少了。
const int maxn = 1e6+10;
int n, m;
ll dp[maxn], arr[maxn], pre[maxn];
int main(void) {
while(~scanf("%d%d", &n, &m) && m) {
for (int i = 1; i<=m; ++i) {
scanf("%lld", &arr[i]);
pre[i] = 0;
}
ll tmp;
for (int i = 1; i<=n; ++i) {
tmp = -LLONG_MAX;
for (int j = i; j<=m; ++j) {
dp[j] = max(dp[j-1], pre[j-1]) + arr[j];
pre[j-1] = tmp;
tmp = max(tmp, dp[j]);
}
}
printf("%lld\n", tmp);
}
return 0;
}
HDU - 1024 - Max Sum Plus Plus(连续子段和++)
原文：https://www.cnblogs.com/shuitiangong/p/12653818.html