#define NUM 101 int a[NUM]; int maxsum(int n) { int sum=0,b=0;for(int i=1; i<=n; i++){if(b>0) b+=a[i];else b=a[i];if(b>sum) sum=b;}return sum; }

我個人認為子段和問題有兩個關鍵點，對當前最大值的判定和對全局最大值的判定。
對當前最大值判定很簡單，就是當前最大值是否大于0，如果大于0加上這個值。不然就把當前最大值更改為后一個值（因為如果此時當前最大值應經<=0了，你再加上一個數a[i]必定<=這個數a[i]本身）。
如果當前最大值比全局最大值要大，就把當前最大值賦給全局最大值。
我們來看一組數字：1，-3 , 7 ，8 ，-4 , 12，-10 , 6
很多時候我會想怎么就能認為全局最大值會成功更新呢。
根據上面那一組數，7+8=15,后，當前最大值和全局最大值都更新為15，-4后當前最大值更新為11，而全局最大值依舊為15，再加上12后當前最大值和全局最大值都更新為23。
例題

總結

以上是生活随笔為你收集整理的动态规划最大子段和问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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