求連續子數組的最大和問題

代碼不重要！重要的是思想過程(括弧 好難啊！！！)

輸入的數組為{1，-2，3，10，-4，7，2，-5}，和最大的子數組為{3，10，-4，7，2}，輸出連續子數組的最大和是18。

步驟操作累加的子數組和最大的子數組和

1	+1	1	1
2	-2	-1	1
3	拋棄前面的（+1 - 2 ） ，加3	3	3
4	+10	13	13
5	-4	9	13
6	+7	16	16
7	+2	18	18
8	-5	13	18

動態規劃：

f(i)表示第i個數字結尾的子數組的最大和

求max[f(i)]

當第 i-1 個數字結尾的子數組中所有數字的和小于0時，如果把這個數再和下一個數字相加，那么求出的和，反而比下一個數字本身還小了，所以就從第i個數字作為起點開始計算

如果第i-1個數字和下一個數字和大于0，那么就相加。

遞歸公式：
$$f(i)=\{\begin{array}{l}pData,i=0或者f(i?1)\le 0\\ f(i?1)+pData[i],i!=0并且f(i?1)>0\end{array}$$

總結

以上是生活随笔為你收集整理的动态规划学习笔记1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。