動態規劃法-------最大連續子序列和

動態規劃法解決最大連續子序列和

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

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

代碼如下：

最大連續字段和時間復雜度為O(N)

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

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

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

狀態方程為: 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]的最大連續子序列之和

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) 編輯收藏引用所屬分類: 算法相關

Feedback

# re: 動態規劃法-------最大連續子序列和[未登錄] 2013-04-10 17:20 123

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

# re: 動態規劃法-------最大連續子序列和[未登錄] 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 而事實上等于 34 回復更多評論

# re: 動態規劃法-------最大連續子序列和 2013-10-05 06:41 456

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

刷新評論列表

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

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

動態規劃法-------最大連續子序列和

動態規劃法解決最大連續子序列和

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

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

代碼如下：

Feedback

# re: 動態規劃法-------最大連續子序列和[未登錄] 2013-04-10 17:20 123

# re: 動態規劃法-------最大連續子序列和[未登錄] 2013-04-10 17:24 123

# re: 動態規劃法-------最大連續子序列和 2013-10-05 06:41 456

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

動態規劃法-------最大連續子序列和

動態規劃法解決最大連續子序列和

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

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

代碼如下：

Feedback

# re: 動態規劃法-------最大連續子序列和[未登錄] 2013-04-10 17:20 123

# re: 動態規劃法-------最大連續子序列和[未登錄] 2013-04-10 17:24 123

# re: 動態規劃法-------最大連續子序列和 2013-10-05 06:41 456

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

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