最長遞增子序列
看板Prob_Solve (計算數學 Problem Solving)作者pinglunliao (王者：一條孤獨的不歸路)時間18年前 (2006/11/16 00:27)推噓7(7推 0噓 2→)留言9則, 4人參與討論串1/2 (看更多)
題目：
假設A是一含有N個相異整數的陣列。試設計一程式找出A中最長遞增子序列(Longest
increasing subsequence) ，
若有兩個解以上，則輸出總和為最大的那一組。
例如A中元素值若為 7，6，23，24，20，18，22 則其最長遞增子序列為
7 23 24、6 23 24、7 18 22
7 20 22、6 18 22、6 20 22
總和最大是 7 23 24 這一組。
底下是我的想法：
先求出最長遞增子序列的長度為3(利用dynamic programming可求出)，再將序列切割成幾
個集合，每個集合內的元素都是遞減
7 6 | 23 | 24 20 18 | 22
從左到右分別對每個集合取最大值
7 6 取最大的為 7
23 取最大的為 23
24 20 18 取最大的為 24 ==> 取了三個了，所以 7 23 24 為解
不知道這個方法對不對？
--
蟄伏秋山待楓紅，青臨洛水無雲彩
麒麟降世多磨難，江郎願使盡長才。 <臥江子>
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 00:30, , 1F
11/16 00:30, 1F
推
11/16 00:57, , 2F
11/16 00:57, 2F
→
11/16 00:58, , 3F
11/16 00:58, 3F
→
11/16 00:59, , 4F
11/16 00:59, 4F
推
11/16 05:58, , 5F
11/16 05:58, 5F
推
11/16 16:34, , 6F
11/16 16:34, 6F
推
11/16 16:35, , 7F
11/16 16:35, 7F
推
11/16 16:36, , 8F
11/16 16:36, 8F
推
11/16 16:41, , 9F
11/16 16:41, 9F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
