http://acm.hdu.edu.cn/showproblem.php?pid=1024
题意就是求你n个数字m段和的最大值
用动态规划求dp[n][m] 表示用前m个数划分为n块的最大和
转移方程为 dp[n][m]=max(dp[n][m-1]+a[m],max(dp[n-1][t])+a[m]),其中dp[n][m-1]+a[m]表示第m个在前i块中 后面表示的是在自己独立变成一个块（1<=t<=m-1）
那么问题来了如果 用这种方法 复杂度为（n^3）因此我们要化简一下，求max(dp[n-1][t])的时候重复求了一些过程，因此只需要改成 设一个变量M 表示前1到m-1的最大值 M=max(M,dp[i-1][j-1]);
但是空间上不够，因此用一个滚动数组 dp[2][MAN]；在求M的用到了i-1;
完整代码：
View Code