作者pinglunliao (王者：一條孤獨的不歸路)
看板Prob_Solve
標題Re: 最長遞增子序列
時間Thu Nov 16 17:47:20 2006
以 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
1F：推 march20:沒有仔細看, 不過確定你的 5 下面應該放 2 才對 11/16 19:05
※ 編輯: pinglunliao 來自: 140.130.34.88 (11/16 20:25)
2F：推 pinglunliao:謝謝樓上的指正 11/16 20:25
3F：推 pinglunliao:今天才發現切割的動作是多餘的... 11/18 00:09
4F：推 godgunman:O(nlogk)的做法, 直接輸出就是和最大了 01/08 17:16