動態規劃法-----最長增序子序列(非連續)

動態規劃法求最長非連續增序子序列

問題描述

一個整形數組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個遞增子序列長度為2， a0 a2 a5 a6為一個遞增序列，其長度為4，且為最長的遞增子序列。

解決方案

設b[j]為以a[j]結束的最長遞增序列的長度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。問題的答案為max(b[j]) 1<= j <= n 。

解決方法類似求最大連續子序列和的問題。

代碼如下

定義s[i] 表示第i個位置處，以a[i]為結尾的最大遞增長度

先求每個位置處的最大長度，然后遍歷求最大長度即可

下面一步增加一個存儲結構，存儲究竟是哪幾個數組構成了遞增的最大長度的數組

#include <iostream>

using namespace std ;

const int N = 1010 ;

int s[N] ;

int a[N] ;

int p[N] ; //p[i] 表示以a[i]結尾的最長子串的前一個節點的標號

int main()

{

int n , i , k;

scanf("%d" , &n) ;

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

{

scanf("%d" ,&a[i]);

s[i] = 1 ;

p[i] = i ; //初始化每一個路徑

}

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

{

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

{

if(a[i] > a[k])

{

int q = s[k] + 1 ;

if(s[i] < q)

{

s[i] = q ;

p[i] = k ;

}

int max = 0 ;

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

{

if(s[max] < s[i])

max = i ;

}

printf("%d\n" , s[max]) ;

while(1)

{

printf("%d->" , a[max]) ;

if(max == 0)

break ;

max = p[max] ;

}

system("pause");

return 0 ;

}

posted on 2011-04-21 14:11 kahn 閱讀(1908) 評論(3) 編輯收藏引用

Feedback

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-10 17:14 wangyan

讀師兄博客受益匪淺。。
PS：我覺得if(max == 0)
打印的時候應當改為if（max==P[max]）
不然的話，若增序列不是從第一個開始，比如100 1 2 3 4，就會死循環。回復更多評論

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-20 17:46 杜明

@wangyan
我的垃圾博客就怕誤人子弟，我都是很隨意的寫的。
http://blog.csdn.net/v_JULY_v/
這個網址是csdn上一個大牛寫的，非常好。各種算法還有分析。推薦你看看。回復更多評論

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-20 17:47 杜明

我的垃圾博客就怕誤人子弟，我都是很隨意的寫的。
http://blog.csdn.net/v_JULY_v/
這個網址是csdn上一個大牛寫的，非常好。各種算法還有分析。推薦你看看。回復更多評論

刷新評論列表

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



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

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

動態規劃法-----最長增序子序列(非連續)

動態規劃法求最長非連續增序子序列

問題描述

一個整形數組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個遞增子序列長度為2， a0 a2 a5 a6為一個遞增序列，其長度為4，且為最長的遞增子序列。

解決方案

設b[j]為以a[j]結束的最長遞增序列的長度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。問題的答案為max(b[j]) 1<= j <= n 。

解決方法類似求最大連續子序列和的問題。

代碼如下

Feedback

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-10 17:14 wangyan

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-20 17:46 杜明

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-20 17:47 杜明

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

動態規劃法-----最長增序子序列(非連續)

動態規劃法 求最長非連續增序子序列

問題描述

一個整形數組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個遞增子序列長度為2， a0 a2 a5 a6為一個遞增序列，其長度為4，且為最長的遞增子序列。

解決方案

設b[j]為以a[j]結束的最長遞增序列的長度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。 問題的答案為max(b[j]) 1<= j <= n 。

解決方法類似求最大連續子序列和的問題。

代碼如下

Feedback

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-10 17:14 wangyan

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-20 17:46 杜明

# re: 動態規劃法-----最長增序子序列(非連續) 2011-08-20 17:47 杜明

動態規劃法求最長非連續增序子序列

一個整形數組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個遞增子序列長度為2， a0 a2 a5 a6為一個遞增序列，其長度為4，且為最長的遞增子序列。

設b[j]為以a[j]結束的最長遞增序列的長度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。問題的答案為max(b[j]) 1<= j <= n 。

解決方法類似求最大連續子序列和的問題。