しらとりのブログ

社会人ひよこプログラマのtil

C#で最長増加部分列(LIS)の実装サンプル

競プロTips勉強メモです。

挿入ソートの最悪計算量は  Ο(n^ 2) です。制約下のカードの最大数 3*10^ 4 でそのまま挿入ソートを実装するとTLEしそうです。(※)

ここでは昇順になっていないカードを一回で正しい位置に挿入する操作ができるので、逆に配列のなかで既に昇順になっている部分列のうち最長のものの長さを計算することで答えが求まります。 入力例1の135246が与えられた場合は、1346というような部分列の長さを求めればよいことになります。

以下、C#での最長増加部分列(LIS:Longest Increasing Subsequence)の長さを求めるサンプルコードです。 配列の長さをインデックス、長さに対応する部分列の最後の値の最小値をアイテムとする動的計画法での実装です。
このdpテーブルは単調増加なので更新箇所の探索は二分探索で行うことができます。
計算量は Ο(n\log n) になります。

Longest Increasing Subsequence(LIS) with C#

※ 実は Ο(n^ 2)解でも通ってしまいます。