数学考试的拓展题：

简单题意：将n个数的数列分为m个不相交的连续子序列，求这m个子段的最大值。

首先容易考虑用dp优化暴力做法。
我们考虑dp[i][j] 表示以j结尾且前j项被分为i段的最大值
那么有两种情况：
1.dp[i][j] = dp[i - 1][k] + a[j] (表示的是第j个元素单独在一组)
2.dp[i][j] = dp[i][j - 1] + a[j] (表示的是第j个元素与前面在同一组内)
于是转移方程就是 dp[i][j] = max(dp[i - 1][k], dp[i][j - 1]) + a[j]; 其中k=i-1，i，...，j-1。
复杂度是O(n^3), 显然对于n<=5000的复杂度是不够的。
接下来我们就需要优化时间，由转移方程可知如果我们枚举i，那么i这一层只和i层和i-1层有关，那么我们可以从小到大枚举j,并且用一个数组ma[n]去保存i-1层的dp[i - 1][k]的数据。ma[j - 1]存的是max(dp[i - 1][i - 1], dp[i - 1][i]...,dp[i - 1][j - 1])

for (int i = 1; i <= m; i++){
    maxx = -inf;
    for (int j = i; j <= n; j++){
        dp[i][j] = max(dp[i][j - 1], ma[j - 1]) + a[j];
        ma[j - 1] = maxx;
        maxx = max(dp[i][j], maxx);
    }
}

不难发现dp的第一维可以省略。可以优化到下面的代码。

for (int i = 1; i <= m; i++){
    maxx = -inf;
    for (int j = i; j <= n; j++){
        dp[j] = max(dp[j - 1], ma[j - 1]) + a[j];
        ma[j - 1] = maxx;
        maxx = max(dp[j], maxx);
    }
}