LIS (Longest Increasing Subsequence) とは最長単調増加シーケンスのこと。数字列(あるいは文字列等、互いに大きさの比較ができるものなら何でもOK)の中から、値が大きくなっていき、もっとも長いシーケンス(数字列)を見つけ出すアルゴリズムのことです.

 -7, 10, 9, 2, 3, 8, 1

例えば,上の数字列では,LIS は -7 2 3 8 になり、その長さは4だ。

また、概念は同じだが、LDS (Longest Decreasing Subsequence、最長単調減少シーケンス) というのもある。

ここでは、i (1<=i<=N、Nはシーケンスの長さ)番目から始まるLIS(またはLDS)の長さについて考える。

上の例では、LIS[i] = { 4, 1, 1, 3, 2, 1, 1 }
      LDS[i] = { 1, 3, 2, 2, 2, 1, 1 } となる。

各データの位置から、LIS(LDS)の長さが分かれば、LISシーケンスを作り出すことができる。

計算時間は O(N^2) 。

下のコードはO(nlogn)の高速バージョン。LISのみになっているが、LDSへの対応もそれほど困難ではないだろう。

Comments are closed.

Post Navigation