問題描述：
最大子段和問題是將一個n個整數的序列a[1]，a[2]….a[n]中字段a[first]….a[last]之和，(1<=first<=last<=n)求這些子段和中最大的。
例如（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)時，最大子段和為20，子段為a[2],a[3],a[4]。

求解方法：
如果不會算法，那就用時間復雜度為O(n^3)的枚舉，i為從1到n的起點，j為從i到n的終點，k為從i到j的子段之和。
還是枚舉，改進一下，得到O(n^2)的枚舉算法，就是將k去掉，在找其終點j的時候就將子段和記錄下來，因為從i到j的子段和就是從i到j-1的子段和加上a[j]。
再改進一下，將這個序列分成1到(1+n)/2的序列與(1+n)/2到n的序列。那么最大的子段有可能出現在：
1.左側序列。2.右側序列。3.跨越中間點的序列。
我們從中間點兩側找最大子段，再找越過中間點的最大子段，就形成了我們所說的分治算法，得到復雜度為O(nlogn)的算法。
其實，我們在選擇一個元素a[j]的時候，只有兩種情況，將a[i]至a[j-1]加上，或者從a[j]以j為起點開始。我們用一個數組dp[i]表示以i為結束的最大子段和，對于每一個a[i]，加上dp[i-1]成為子段，或以a[i]開始成為新段的起點。因為我們只需要記錄dp值，所以復雜度是O(n)。
這就是最大子段和的動態規劃算法。
我們甚至不需要dp數組，只需要定義一個dp變量，因為最后要求的dp值也是最大的，所以我們可以在求dp的時候更新為最大的。

暴力法：

#include<iostream> using namespace std;int MaxSum(int n,int *a,int &besti,int &bestj) {int sum=0;for(int i=0;i<n;i++){for(int j=i;j<n;j++){int tempSum=0;for(int k=i;k<j;k++){tempSum+=a[k];if(tempSum>sum){sum=tempSum;besti=i;bestj=j;}}}}return sum; } int main() {int a[100]={-2,11,-4,13,-5,-2};int n=6;int besti=0;int bestj=0;MaxSum(n,a,besti,bestj);cout<<"輸出最大子段和：";for(int i=besti;i<bestj;i++){cout<<a[i]<<" ";}}

暴力法改進：

#include<iostream> using namespace std;int MaxSum(int n,int *a,int &besti,int &bestj) {int sum=0;for(int i=0;i<n;i++){int tempSum=0;for(int j=i;j<n;j++){tempSum+=a[j];if(tempSum>sum){sum=tempSum;besti=i;bestj=j;}}}return sum; } int main() {int a[100]={-2,11,-4,13,-5,-2};int n=6;int besti=0;int bestj=0;MaxSum(n,a,besti,bestj);for(int i=besti;i<=bestj;i++){cout<<a[i]<<" ";}}

動態規劃：

#include<iostream> using namespace std;int MaxSum(int n,int *a,int &besti,int &bestj) {int sum=0;int tempSum=0;for(int i=0;i<n;i++){if(tempSum>0){tempSum+=a[i];}else{tempSum=a[i];}if(tempSum>sum){sum=tempSum;}} return sum; } int main() {int a[100]={-2,11,-4,13,-5,-2};int n=6;int besti=0;int bestj=0;cout<<MaxSum(n,a,besti,bestj);}

總結

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

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