内容別リスト/データ探索系/最長増加部分列 - 競技プログラミング用 知識集積所

---

雑な説明

数列の一部（連続でなくてもよい）を拾って単調増加列を作るとき、最長でどのくらいの長さのものを作れるか？という問題。
動的計画法の応用で解ける。

レベル

ABCのE問題以降。

アルゴリズム内容

例えば

A = {1, 4, 3, 5, 2}

という数列があったとする。
この場合、

B = {1, 4, 5}

という数列は単調増加していて、しかもAから「数列の一部だけを拾う」という方法で作ることができる。
こういう場合、BはAの増加部分列という。
増加部分列の中で最も長いものを最長増加部分列といい、これを求めたり利用する問題を競プロでときどき見かける。
これは、動的計画法を用いて以下のような方法で解ける。

まず、Aと同じ長さのvector（ここではlen）と、空のvector（ここではvec）を用意する。
lenは、そこで数列を打ち切った場合の最長増加部分列の長さ。
vecは、その長さの最長増加部分列の末尾の最小値。

A	1	4	3	5	2
len	？	？	？	？	？

vec

最初のデータである1を見て、vecの中でそれより小さい数が何個あるかを二分探索※で探す。
それをlenの方に書き込む。
vecの書き込んだ数に対応する位置にAの中身を書き込む（長さが足りなければ伸ばす）。

A	1	4	3	5	2
len	0	？	？	？	？

vec

1

次のデータである4を見て、vecの中でそれより小さい数が何個あるかを二分探索※で探す。
それをlenの方に書き込む。
vecの書き込んだ数に対応する位置にAの中身を書き込む（長さが足りなければ伸ばす）。

A	1	4	3	5	2
len	0	1	？	？	？

vec

1

4

次のデータである3を見て、vecの中でそれより小さい数が何個あるかを二分探索※で探す。
それをlenの方に書き込む。
vecの書き込んだ数に対応する位置にAの中身を書き込む（長さが足りなければ伸ばす）。

A	1	4	3	5	2
len	0	1	1	？	？

vec

1

3

次のデータである5を見て、vecの中でそれより小さい数が何個あるかを二分探索※で探す。
それをlenの方に書き込む。
vecの書き込んだ数に対応する位置にAの中身を書き込む（長さが足りなければ伸ばす）。

A	1	4	3	5	2
len	0	1	1	2	？

vec

1

3

5

次のデータである2を見て、vecの中でそれより小さい数が何個あるかを二分探索※で探す。
それをlenの方に書き込む。
vecの書き込んだ数に対応する位置にAの中身を書き込む（長さが足りなければ伸ばす）。

A	1	4	3	5	2
len	0	1	1	2	1

vec

1

2

5

最終的にできたvecの大きさが最長増加部分列の長さである。
長さを答えるだけなら、これで終わり。
というか、実はlenの方も真面目に作る必要がない。

やや難しいのは、実際に最長増加部分列を構成する点。
vecは最終的に{1,2,5}という数列になっているが、2は5より後ろにあるため、これは増加部分列にはなっていない。
正しく復元するには、後から上書きされた影響を剝がす必要がある。

そこで、以下のようにする。

• 長さが3なので、それより1小さい2という数を、lenで後ろから探す
• 最初に見つかった場所のAの値は5なので、それが最長増加部分列.at(2)の中身
• 探す値を1減らして1という数を、lenで続きから逆方向に探す
• 最初に見つかった場所のAの値は3なので、それが最長増加部分列.at(1)の中身
• 探す値を1減らして0という数を、lenで続きから逆方向に探す
• 最初に見つかった場所のAの値は1なので、それが最長増加部分列.at(0)の中身

こうして、{1,3,5}という最長増加部分列が復元される。

最長増加部分列は1つとは限らないが、普通の問題であれば別解として認められる。

C++実装例。

vector<int> lis(vector<int> original) {
  int n = original.size();
  vector<int> len(n);
  vector<int> vec;
  vec.reserve(n);
  for (int i=0; i<n; i++) {
    len.at(i) = distance(vec.begin(),lower_bound(vec.begin(),vec.end(),original.at(i)));
    if (len.at(i)==vec.size()) vec.emplace_back(original.at(i));
    else vec.at(len.at(i)) = original.at(i);
  }
  vector<int> result(vec.size());
  int idx = vec.size()-1;
  for (int i=n-1; i>=0; i--) {
    if (len.at(i)==idx) {
      result.at(idx) = original.at(i);
      idx--;
    }
  }
  return result;
}

注意点

関連アルゴリズム

動的計画法

再帰的問題、つまり「少し小さい問題の答えがわかっていれば簡単に答えが出る」というタイプの問題を高速に解くアルゴリズム。
最長増加部分列を求めるのに使われている。

バックトレース

終了状態から逆再生しながら何かを調べるアルゴリズム。
最長増加部分列そのものを復元するためにお世話になる。

最長共通部分列

2つの数列または文字列の一部（連続でなくてもよい）を拾って全く同じ数列または文字列を作るとき、最長でどのくらいの長さのものを作れるか？という問題。
実は最長共通部分列を最長増加部分列のアルゴリズムで解く方法がある。