Zenn
📈

【競プロ】最長増加部分列(LIS)

2024/03/25に公開
AtCoder
アルゴリズム
tech

はじめに

今回は 最長増加部分列(LIS) を求めるアルゴリズムについて、お気持ちから実装まで解説したいと思います！

最長増加部分列(LIS)とは

数列に対してその部分列であって増加列であるものを増加部分列といい、増加部分列のうち長さが最大なものを最長部分増加列といいます。

数列に対するその部分列は、順序を変えずに取り出した列（競プロにおいては空列は含まないことが多い）のこと。

例
数列\{1, 3, 4, 4, 2, 5\}に対して、\{4\},\{1, 3\},\{1, 2, 5\},\{1, 3, 4, 5\}は増加部分列ですが\{4,4\},\{3, 2\},\{1, 4, 2\}は増加部分列ではありません。

アルゴリズム

お気持ち

配列のi番目までで作れる増加部分列を考える。
増加部分列のj番目の要素のうちの最小値を記録していく。

具体例

配列A={1, 3, 4, 4, 2, 5}
記録する配列DP

  • DPをINFで初期化

    j 0 1 2 3 4 5
    DP INF INF INF INF INF INF

  • 配列Aのi=0までの要素{1}で増加部分列{1}が作れるためDP[0]を更新

    j 0 1 2 3 4 5
    DP 1 INF INF INF INF INF

  • 配列Aのi=1までの要素{1,3}で増加部分列{1,3}が作れるためDP[1]を更新
    （増加部分列{3}も作れるが、DP[0]を更新できないため

    j 0 1 2 3 4 5
    DP 1 3 INF INF INF INF

  • 配列Aのi=2までの要素{1,3,4}で増加部分列{1,3,4}が作れるためDP[2]を更新

    j 0 1 2 3 4 5
    DP 1 3 4 INF INF INF

  • 配列Aのi=3までの要素{1,3,4,4}ではDPは更新できない

    j 0 1 2 3 4 5
    DP[i] 1 3 4 INF INF INF

  • 配列Aのi=4までの要素{1,3,4,4,2}で増加部分列{1,2}が作れるためDP[1]を更新

    j 0 1 2 3 4 5
    DP 1 2 4 INF INF INF

  • 配列Aのi=5までの要素{1,3,4,4,2,5}で増加部分列{1,3,4,5}が作れるためDP[3]を更新

    j 0 1 2 3 4 5
    DP 1 2 4 5 INF INF

DPの更新の際に、Aのi=kまでの要素の増加部分列を調べている計算量が大きくなってしまう。
具体例のDPの更新を見ると次のことがわかる。

i=kのとき、DPのA[k]以上のインデックスが最小の要素をA[k]で更新している

これは、具体例で更新できない場合も含む。

証明

DP_i(j)を数列A_0, \dots, A_iから得られる増加部分列のj番目の要素の最小値とする。
このとき、DP_{i+1}は、

DP_{i+1}(j)=\begin{dcases} DP_{i}(j) &\text{if } j \neq \argmin\{l|DP_i(l) \ge A_{i+1}\} \\ A_i &\text{if } j = \argmin\{l|DP_i(l) \ge A_{i+1}\} \end{dcases}

の漸化式で求まる。

DPは増加列であること

i=0のとき正しい。
数列A_0, \dots, A_{i+1}から得られる増加部分列をSとするとき

DP_{i+1}(j)=\min_S\{DP_{i}(j),S_j\}

であり、\min_S\{DP_{i}(j),S_j\}<DP_{i}(j)<DP_{i}(j+1), \min_S\{DP_{i}(j),S_j\}<S(j)<S(j+1)であるから、\min_S\{DP_{i}(j),S_j\}<\min_S\{DP_{i}(j+1),S_{j+1}\}となる。

DP_{i+1} \neq DP_{i}のとき

DP_{i+1}とDP_{i}が異なるとき、数列A_0, \dots, A_{i+1}から得られる増加部分列のうち、数列A_0, \dots, A_{i}から得られる増加部分列とは異なる部分増加列Sが存在する。（そうでなければDP_{i+1}=DP_{i}となる）
したがって、SはA_{i+1}を含む。特に、Sの末項がA_{i+1}である。
このとき、DP_{i+1}(j)=\min\{DP_{i}(j),S_j\}である。Sの末項を除く数列S'は数列A_0, \dots, A_{i}から得られる増加部分列なので、DP_{i}(j)\le S'(j)である。
つまり、DP_{i+1}(j)=DP_{i}(j) \quad j\le |S'|である。
DP_{i+1}とDP_{i}は異なるので、|S|=kとするとDP_{i+1}(k)=A(i+1)\neq DP_{i}(k)である。したがって、DP_{i+1}とDP_{i}で異なる要素はA_{i+1}である。
このとき、DP_{i+1}は増加列であるからA_{i+1}となる要素はただ一つである。このとき、A_{i+1}となるDP_{i+1}の要素をDP_{i+1}(k)とすると、DP_{i+1}(k-1)<A_{i+1}かつDP_{i+1}(k-1)>A_{i+1}である。DP_{i+1}とDP_{i}で異なる要素はA_{i+1}だけなので、DP_i(k-1)<A_{i+1}かつDP_i(k-1)>A_{i+1}でk=\argmin\{l|DP_i(l) \ge A_{i+1}\}となる。

DP_{i+1} = DP_{i}のとき

上記の漸化式は正しい。

コード

lis
vector<long long> LIS(vector<long long> A) {
  long long N = A.size();
  long long INF=(1LL<<60);
  vector<long long> DP(N, INF);

  rep(i,N){
    auto itr = lower_bound(DP.begin(),DP.end(), A[i]); // A[i]以上のDPの要素へのイテレータを取得
    *itr = A[i]; // イテレータが指す要素をA[i]に更新
  }

  return DP;
}

参考

https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5

Discussion