Re: 最長遞增子序列
看板Prob_Solve (計算數學 Problem Solving)作者pinglunliao (王者：一條孤獨的不歸路)時間18年前 (2006/11/16 17:41)推噓4(4推 0噓 0→)留言4則, 3人參與討論串2/2 (看更多)
以 16 12 8 4、15 11 7 3、14 10 6 2、13 9 5 1 序列為例
16 12 8 4 | 15 11 7 3 | 14 10 6 2 | 13 9 5 1
先切出遞減的子序列如上圖
然後分別對每個子集合內的元素做可以最佳子序列長度的選擇
16 12 8 4 | 15 11 7 3 | 14 10 6 2 | 13 9 5 1
best length 1 1 1 1 | 2 2 2 1 | 3 3 2 0 | 4 3 2 1
以 3 這個數字來講，它在第二個集合內
但是它沒有比第一個集合內的任一個數字(元素)來的大
所以它所能組成的最長子序列就只有它自己 3 (長度為 1 )
再舉 10 為例，它在第三個集合內，但它有比第二個集合內的元素 7 來的到
所以 10 的最佳長度為 2 ( 7 的最佳長度)+ 1( 10 自己)
然後由 右 向 左 挑出長度為 4 的最大值 13 ，再向左找出長度為 3 且小於 13 的數
再找出長度為 2 的 、長度為 1 的 會得到 4 7 10 13
目前我用這個做法還沒有找到反例的~~~
--
蟄伏秋山待楓紅，青臨洛水無雲彩
麒麟降世多磨難，江郎願使盡長才。 <臥江子>
http://www.wretch.cc/blog/pinglunliao/ 我目前常用的個人網誌
http://pinglunliao.blogspot.com/ 以前在用的
http://blog.yam.com/pinglunliao/ 申請好玩的
http://blog.xuite.net/pinglunliao/pinglunliao/ 快癈了！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.130.34.88
推
11/16 19:05, , 1F
11/16 19:05, 1F
※ 編輯: pinglunliao 來自: 140.130.34.88 (11/16 20:25)
推
11/16 20:25, , 2F
11/16 20:25, 2F
推
11/18 00:09, , 3F
11/18 00:09, 3F
推
01/08 17:16, , 4F
01/08 17:16, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
