作者pinglunliao (王者：一條孤獨的不歸路)
看板Prob_Solve
標題最長遞增子序列
時間Thu Nov 16 00:30:01 2006
題目：
假設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
1F：推 LPH66:但你不能保證前三個就一定是你要的... 11/16 00:30
2F：推 pinglunliao:樓上的說到我的困難點，因為我是猜的，不知道怎麼證明 11/16 00:57
3F：→ pinglunliao:這個方法對不對。 11/16 00:58
4F：→ pinglunliao:想不出反例來 11/16 00:59
5F：推 Fenikso:5 3 1, 4 2 <= 不能取最大的 因為5 4不是遞增 11/16 05:58
6F：推 march20:這是 DP 經典題, 把 A[1,1], A[1,2], A[1,n-1] 求完 11/16 16:34
7F：推 march20:A[1,n] 的解自然就冒出來了 11/16 16:35
8F：推 march20:啊, 不對, 其實要更麻煩點, 直接回文好了 11/16 16:36
9F：推 march20:漏看第二個條件了, 再重新想過 @@ 11/16 16:41