之所以想到要注释一下，没别的意思，只是因为几个月前刚学DP，完全看不懂，前几天费了几个小时终于看懂了，注释下来，能使自己整理一下思路，也作为自己的一篇日记。
当时我能看懂时间和空间均为O(MN^2)的函数，但可能由于自己看书是直接从动态规划一章看起，书上对于经过优化的函数也没有更多的解析，当时看起来完全不知所云。前几天看的时候，是对着方程结合书上的几句话自己去理解，尝试自己动手去写，但错了。看书上代码，都要自己去理解那些变量数组是干什么用的，感觉也是非常吃力。
1，
我觉得理解那个优化函数，必须先要充分理解那个二维的DP方程：
b[i][j]=max(b[i][j-1]+a[j],max(b[i-1][t])+a[j]) (i-1<=t<j)
b[i][j]表示的是第i段在前j项（含第j项）的最大值。对于b[i][j]含有第j项必须要理解好！则方程的意思是：对于a[j]项，要么将它加到第i段，要么它自己作为新的一段。
注意到方程外层的max选择，都要加上a[j]这一项。这里可能很容易产生一个疑问，如果a[j]是一个负数，为什么还要加上a[j]呢？回到b[i][j]所表示的意义上解释，由于b[i][j]表示的是含有第j项的最大值，所以a[j]是肯定要加进来的。假使a[j]是一个负数，它加进来了也不会影响在第i段中前j-1项的最大值。
所以第m段的最大值，并不是b[m][n]，而是b[m][m~n]之间的最大值。
同样道理，第i-1段的最大值是b[i-1][t],(i-i<=t<j)。
2，
理解了上述的DP方程后，再来考虑优化，正如书上所说的，由于在第i段中，只用到第i段和第i-1段的值。如果采用一维数组存储b[]，只要在计算第i段的时候，没有去改变第i-1段保留下来的值即可。再考虑到，内层max选择，需要用到第i-1段在i-1到j-1位置的最大值，不但要进行重复计算，也影响到b[j]的计算，因为j前面的值既要用作b[j]的计算，也要更新作为下一段i+1计算时所用。
为了解决这个问题，书上是利用了一个辅助的一维数组c[]，c[j]保存的是上一段i-1在j位置的最大值。显然计算第i段在j位置的值b[j]要用到的c[]的下标是从i-1到j-1的。
那么这时DP方程可以变为：
b[j]=max(b[j-1]+a[j],c[j-1]+a[j])
要注意，b[j-1]与c[j-1]是相差一段的，即b[j-1]计算的是第i段的值，而c[j-1]记录的是i-1段的值。
这里有一个关键是对c[]在计算第i段值b[j]的时候，要及时更新，以作计算下一段使用。
3，
以上的具体实现自己写不出来，还是照看书上的代码，略作解析。其实明白了上面说明的两段，书上代码是很好理解的。书上对于边界条件的处理，我觉得做得非常好，而我也正是错在这个地方。
int MaxSum(int m,int n,int *a)
{
if(n<m||m<1) return 0;
int *b=new int[n+1]; //b[j]保存的是第i段中在前j（含j）项的最大值
int *c=new int[n+1]; //c[j]保存的是i-1段中在i-1到j（含j）项中的最大值
//注意，以上b[j]和c[j]都是指在计算第i段时的值；
b[0]=0;
c[1]=0; //第0段时的两个值，初始化边界条件
for(int i=1;i<=m;i++) //i为当前计算段数
{
b[i]=b[i-1]+a[i]; //b[i]即b[j]在j=i时的值，由于j=i，每一个项都要成为一段，这就是边界条件
c[i-1]=b[i]; //这里很绕，其实这句是没用的，因为在第i段中数组c[]保存的值是为下一
//段i+1服务的，i+1段只用到c[i]，可以直接删掉，免得误导
int max=b[i]; //max记录第i段的从i位置开始所有能用到的项的最大值
for(int j=i+1;j<=i+n-m;j++)
{
b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];//这里用到的c[j-1]
//是没被修改的，还是上一段i-1中在j-1位置的最大值
c[j-1]=max; //用完后就要修改为第i段中在j-1位置的最大值，明显，max是记录了第i段中的
if(max<b[j]) //在j-1位置的最大值，尽管当前循环中计算的是第j项
max=b[j]; //更新max的值
}
c[i+n-m]=max; //由于max记录的项总比循环的j项小1，所以第i段在最后一项中的最大值放在循环外更新
}
int sum=0; //默认全是负数的时候，最大值是0,如果要计算负的最大值，可以将sum设为一个大负数
for(int j=m;j<=n;j++) //为什么还有一次循环找最大值，而不是直接使用b[n]呢？因为b[j]包含了a[j]，
if(sum<b[j]) //在b[j]的值不一定比不包含a[j]的其他项大。
sum=b[j];
return sum;
}
附：pku 2479就是一题求最大2段和。