動態(tài)規(guī)劃法-------最大連續(xù)子序列和

動態(tài)規(guī)劃法解決最大連續(xù)子序列和

     問題描述：
       數(shù)組 int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某幾個連續(xù)的子序列其和最大，比如a0+a1 = -1 。a1+a2+a3+a4 = 78 。則a1 a2 a3a4組成的數(shù)組即是所求。

     解決方法：
        此題嘗試使用動態(tài)規(guī)劃的方法進(jìn)行解決，首先建立狀態(tài)方程。
       設(shè)b[j]表示第j處，以a[j] 結(jié)尾的子序列的最大和。
       則b[j] = max(a[j] + b[j-1] , a[j]) ，而我們的所求的答案，就是從1- n對b數(shù)組求最大值。

代碼如下：

最大連續(xù)字段和時(shí)間復(fù)雜度為O(N)

定義b[j]為數(shù)組中包含a[j]的最大連續(xù)子序列和

注意一個誤區(qū)，b[j] 并不是1-j中最大的連續(xù)子序列的和，只是包含a[j]的最大子序列的和

而我們所要求的是求出b[j]中最大的值，即為所求

狀態(tài)方程為: b[j] = max(b[j-1] + a[j] , a[j])

#include <iostream>

using namespace std ;

const int N = 8 ;

int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ;

int b[N] ; //b[i]表示包含a[i]的最大連續(xù)子序列之和

inline int max(int a , int b)

{

return (a > b) ? a : b ;

}

int main()

{

b[0] = a[0] ;

int i , mam = b[0];

for(i = 1; i < N ; i++)

{

b[i] = max(a[i] , b[i-1] + a[i]);

if(mam < b[i])

mam = b[i] ;

}

printf("max %d\n" , mam) ;

for(i = 0; i < N ; i++)

printf("%d\n" , b[i]) ;

system("pause") ;

return 0 ;

}

posted on 2011-04-21 13:54 kahn 閱讀(9641) 評論(3) 編輯收藏引用所屬分類: 算法相關(guān)

Feedback

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和[未登錄] 2013-04-10 17:20 123

感覺這個是錯的吧 b[j] = max(a[j] + b[j-1] , a[j]) 回復(fù) 更多評論

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和[未登錄] 2013-04-10 17:24 123

比如這種情況
-1 -1 9 9 9 -1 -1
到
-1 -1 9 9 9 -1 -1 9

b[7] == 27
按照你的公式
b[8] == 36 而事實(shí)上等于 34 回復(fù) 更多評論

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和 2013-10-05 06:41 456

@123
誰說的，明明b[7] == 25好吧回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 9-24MTK一面二面微軟筆試總結(jié) 2011-09-07xx移動創(chuàng)業(yè)公司筆試題編程之美2.7 最大公約數(shù) O(n)實(shí)現(xiàn)刪除兩個數(shù)組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

動態(tài)規(guī)劃法-------最大連續(xù)子序列和

動態(tài)規(guī)劃法解決最大連續(xù)子序列和

問題描述：
       數(shù)組 int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某幾個連續(xù)的子序列其和最大，比如a0+a1 = -1 。a1+a2+a3+a4 = 78 。則a1 a2 a3a4組成的數(shù)組即是所求。

代碼如下：

Feedback

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和[未登錄] 2013-04-10 17:20 123

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和[未登錄] 2013-04-10 17:24 123

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和 2013-10-05 06:41 456

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

動態(tài)規(guī)劃法-------最大連續(xù)子序列和

動態(tài)規(guī)劃法解決最大連續(xù)子序列和

問題描述 ： 數(shù)組 int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某幾個連續(xù)的子序列其和最大，比如a0+a1 = -1 。a1+a2+a3+a4 = 78 。則a1 a2 a3a4組成的數(shù)組即是所求。

代碼如下：

Feedback

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和[未登錄] 2013-04-10 17:20 123

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和[未登錄] 2013-04-10 17:24 123

# re: 動態(tài)規(guī)劃法-------最大連續(xù)子序列和 2013-10-05 06:41 456

問題描述：
數(shù)組 int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某幾個連續(xù)的子序列其和最大，比如a0+a1 = -1 。a1+a2+a3+a4 = 78 。則a1 a2 a3a4組成的數(shù)組即是所求。