之所以想到要注釋一下，沒別的意思，只是因為幾個月前剛學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段和。