题意：给m n n个数，求m个连续段的和最大值
状态转移： 以 j 结尾的的 i 个子段和的最值，那么最值一定在这个过程中。
由于以j结尾，对于每个a[j]必须要选，可以让它附在前一段后面也可以让它自成一段。
dp[i][j] = max(dp[i][j-1] a[j], max(dp[i-1][k]) a[j] ) k: i-1~j-1
其中 max(dp[i-1][k])表示前 j - 1项 选取 i-1段以 k 结尾的最大值。
实现这个状态转移需要三层循环，限时 1 s，需要优化
我们发现最内层循环 for(int k=i-1;k<=j-1;k ) dp[i][j] = max(dp[i][j-1] a[j], dp[i-1][k] a[j] )
最终dp[i-1][k]求出来的就是 dp[i-1][ j ] 过程中的某一个值，以 j 结尾比以 k 结尾范围要大。
用一个数组记录即可。
代码语言：javascript复制//HDU - 1024
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6 15;
const int inf = 0x7fffffff;
int dp[maxn],a[maxn],maxc[maxn];
int m,n,ans;
int main()
{
while(~scanf("%d %d",&m,&n)){
for(int i=1;i<=n;i ){
scanf("%d",&a[i]);
}
memset(dp,0,sizeof(dp));
memset(maxc,0,sizeof(maxc));
for(int i=1;i<=m;i ){
ans = -inf;
for(int j=i;j<=n;j ){
dp[j] = max(dp[j-1] a[j], maxc[j-1] a[j]);
maxc[j-1] = ans;
ans = max(dp[j],ans);
}
}
printf("%dn",ans);
}
return 0;
}
