2012年04月17日
Longest increasing subsequence
- 2012-04-17 (Tue)
- 一般
O(n^2)では自明にDPで解ける問題で，なんとなくO(n log n) で解けそうなのだけど……
とか考えていたら普通に wikipedia に載ってた．Longest increasing subsequence は O(n log n) で解けると．これまでに見つかった increasing subsequences を長さ順にソートして（その端点の）テーブルを作っておけばいいのね．長さ順にソートされた上昇列の端点は小さい順に並んでいるから，新しい要素をどこに連結すればいいかが二分探索で O(log n) で出来ると．なるへそ．
O(n^2) の DP で使うテーブルのキーと値を入れ替えた上でキー順にソートしておけばテーブル更新が速いということか．非減少はいかんなぁ．
- Comments: 0
- TrackBack (Close): -