動(dòng)態(tài)規(guī)劃解決問(wèn)題是自底向上。原問(wèn)題的規(guī)模是n個(gè)元
素。這n個(gè)元素不好考慮，我們先考慮n-1個(gè)元素，這樣還不好考
慮，我們考慮n-2個(gè)元素，這樣依次遞減，最后問(wèn)題規(guī)模變成一個(gè)
元素。但是我們發(fā)現(xiàn)，在遞減的過(guò)程中間，子問(wèn)題的最優(yōu)解包含
在原問(wèn)題的最優(yōu)解之中，而且子問(wèn)題的解還有一些是重復(fù)的。
因此，使用動(dòng)態(tài)規(guī)劃來(lái)解決這個(gè)問(wèn)題。

思想：
對(duì)字段序列進(jìn)行一個(gè)循環(huán)，
如果之前的序列b>0，則加入這個(gè)新的序列之中；
如果之前的序列b<=0,則重新設(shè)置字段的序列和為nums[i]；
如果之前的序列加上nums[i],的值大于之前的最大序列和，則更新最大序列和；
我們要寫出一個(gè)遞歸方程。我們?cè)O(shè)置一個(gè)數(shù)組b來(lái)存放最優(yōu)解，首先將b[1]=a[1]，a存放的是我們的n個(gè)元素。第i個(gè)元素，他的狀態(tài)就是將他放不放到數(shù)組b中（和之前的有些像）。因此，遞歸方程就是:b[i]=max{b[i-1]+a[i],a[i]}

#include<iostream> using namespace std;long long MaxSum(long long *nums,int n) {long long sum=0;long long b=0;//b是臨時(shí)的字段和的數(shù)值 for(int i=0;i<n;i++){if(b>0){b=b+nums[i];}else{b=nums[i];}if(b>sum)//更新字段和值 {sum=b;}}return sum; } int main() {cout<<"請(qǐng)輸入字段的長(zhǎng)度：";long long n;cin>>n;long long nums[n];cout<<"請(qǐng)輸入字段序列(中間用空格隔開)：";for(int i=0;i<n;i++){cin>>nums[i];} cout<<"最大字段和為："<<MaxSum(nums,n);return 0; }

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析——动态规划——最大字段和问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。