最長増加部分列・最長共通部分列

競技プログラミングでは、「最長増加部分列（LIS）」や「最長共通部分列（LCS）」を求めるものが出題されることがある。
これらは動的計画法により高速に求めることができる。

ある数列や文字列 $A=(a_1,a_2,...,a_N)$ がある時、部分列（Subsequence）とは、$A$ からいくつかの要素を抽出した列。
飛び飛びでもよいが、順番は元から変わってはいけない。

• $A=(3,1,4,1,5)$ とすると、
  • $(3,1,1,5)$ や $(1,)$ などが部分列
  • $(5,3)$ や $(1,1,4)$ は、元と並びが変わっているため部分列ではない

別の言い方をすると、以下の手順で構築できる列 $C$ が部分列である。

• $A$ の長さを $N$ として、$1 \le i_1 \lt i_2 \lt ... \lt i_k \le N$ を満たす添字列 $(i_1,...,i_k)$ を決める
• $C=(a_{i1},a_{i2},...,a_{ik})$ とする

空の列 $()$ を部分列に含むかどうかは定義による。

$A$ の部分列のうち単調増加なものを $A$ の「増加部分列」という。

同じ値を許すかは定義によるが、ここでは許さない（狭義単調増加）とする。

増加部分列のうち、長さが最も長いものを $A$ の「最長増加部分列」（Longest Increase Subsequence, LIS）という。

LISの具体的な要素は複数通り考えられる場合もあるが、長さは $A$ により一意に決まる。

• 最長共通部分列 - 東京工芸大学
• 最長共通部分列問題

2つの列 $A$ と $B$ に共通する部分列を、$A$ と $B$ の「共通部分列」という。

そのうち長さが最長のものを「最長共通部分列」（Longest Common Subsequence, LCS）という。

LCSの具体的な要素は複数通り考えられる場合もあるが、長さは一意に決まる。

• $A=(1,2,3,4,5,6,7,8,9)$
• $B=(1,3,5,7,9,11,8,2,1)$
• 共通部分列の例
  • $(1,2)$
  • $(3,7,8)$
• 最長共通部分列の例
  • $(1,3,5,7,9)$

動的計画法で求める。このアルゴリズムでは、最長増加部分列の内容自体は求まらない。

大きく分けて、二分探索を用いる方法と、セグメント木を用いる方法がある。前者の方が実装は楽。

• Longest Increasing Subsequence(最長増加部分列) | Luzhiled’s Library

以下のDPをまず考える。

• $\mathrm{DP[i,j]}:=(a_1,...,a_i)$ から取れる長さ $j$ の増加部分列のうち、末尾要素が取り得る最小値

ある増加部分列の末尾に新たな要素 $x$ を追加できるかどうかは、現在の末尾要素が $x$ 未満かどうかさえ分かれば判定できる。
長さが同じなら末尾要素が小さい方が、追加できる $x$ の範囲が広いので、長さ毎に末尾が最も小さいものだけ記録しておけば十分となる。

以下の具体的なアルゴリズムでも示されるが、このDPは $i-1$ と $i$ では更新箇所が1箇所しかない。
よって、DPを2次元配列で持つのではなく、$i$ の次元は省略し、$j$ を添字に持つ1次元配列を破壊的に更新していくことで、より高速に求められる。

1. $L=[-\infty]$ を用意する。
2. $i=1,2,...,N$ の順に以下を1つずつ処理する。現在処理中の要素を $a_i$ とする。
   1. $Lの末尾要素 \lt a_i$ の場合、$L$ の末尾に $a_i$ を追加する。
   2. それ以外の場合、$L$ 上で二分探索して $a_i$ 以上の値が初めて出てくるindex $k$ を求め、$L[k]←a_i$ で置き換える。
3. 最後まで処理した後、$L$ の最大のindexが、最長増加部分列の長さとなる。

計算量 $O(N \log{N})$ で求めることができる。

狭義単調増加の場合はbisect_left（$a_i$ 以上が初めて出てくるindex）だが、広義単調増加の場合はbisect_right（$a_i$ を超える値が初めて出てくるindex）を用いる。

A = (3, 4, 8, 5, 1, 6, 2, 7)

i  Ai   L
        [-∞]
1   3   [-∞, 3]
2   4   [-∞, 3, 4]
3   8   [-∞, 3, 4, 8]
4   5   [-∞, 3, 4, 5]
5   1   [-∞, 1, 4, 5]
6   6   [-∞, 1, 4, 5, 6]
7   2   [-∞, 1, 2, 5, 6]
8   2   [-∞, 1, 2, 5, 6, 7]    →  LIS長は 5

Lを $\infty$ で初期化した長さ $N$ の配列として初期化する流儀もある。
末尾に加えるか更新するかの場合分けが不要となりコードは短くなるが、代わりに毎回二分探索をおこなう必要がある。

Python実装例

二分探索を用いる方法は、実装がシンプルではあるが、拡張性の面ではやや低い。
最長増加部分列を求めるのにはセグメント木を使う方法もあり、そちらは多少、ひねったバリエーション問題にも対応できる。

• たとえば少し改変すると、最長増加部分列の個数を数え上げたりできる
  • yukicoder No.992 最長増加部分列の数え上げ #競技プログラミング - Qiita

以下のDPを定義する。

• $DP[i]=a_i$ を末尾に必ず使用するような増加部分列の中で、最長のものの長さ

$DP[i]=0$（$i=1,...,N$）で初期化した上で、このDP配列をセグメント木に載せる。

$i$ ではなく、$a_i$ が小さい順に処理する。同率の場合は、indexが後の方から処理する。
（※広義単調増加の場合は、前の方から処理する）

$a_i$ について処理する際、$DP$ 配列の「$[1,i)$ の区間における最大値 + 1」が、$DP[i]$ となる。
区間最大値はセグメント木やBITで取得できるので、これで $DP[i]$ を計算し、更新する。

最終的に、$DP$ 全体の中での最大値が答えとなる。

こちらも計算量のオーダーは $O(N \log{N})$ となる。
二分探索と比べて定数倍や必要なメモリは重くなるが、一般的な競技プログラミングの制約の前ではまぁ、だいたい気にしなくていい。

i    1  2  3  4  5  6  7  8
A = (3, 4, 7, 5, 1, 5, 7, 3)

i  Ai   DP
        [0, 0, 0, 0, 0, 0, 0, 0]
5   1   [0, 0, 0, 0, 1, 0, 0, 0]  [1, i)の最大値（波線区間） + 1 で、DP[i] を更新
         ~~~~~~~~~~
8   3   [0, 0, 0, 0, 1, 0, 0, 2]
1   3   [1, 0, 0, 0, 1, 0, 0, 2]
2   4   [1, 2, 0, 0, 1, 0, 0, 2]
6   5   [1, 2, 0, 0, 1, 3, 0, 2]
4   5   [1, 2, 0, 3, 1, 3, 0, 2]
7   7   [1, 2, 0, 3, 1, 3, 4, 2]
3   7   [1, 2, 3, 3, 1, 3, 4, 2]    → LIS長は4

具体的な最長増加部分列の1つを求める場合。

二分探索を用いる方法で、$L$ の他に、以下の情報も持ってDPする。

• $prev[i]$: $a_i$ を更新したとき、$L[k]$ に格納したとして、その時点の $L[k-1]$ の値（先頭の場合は $-\infty$）

最後までDPしたら、復元する。

• $x=L[末尾]$ で初期化する。また、LIS復元用の配列 $S$ を空で初期化する。
• $A$ を逆順に走査する。$a_i=x$ となる $i$ が見つかったら、$S.append(x)$、$x ← prev[i]$ とする
• $x=-\infty$ になったら終了。$S$ を反転したものがLISとなる。

prevの記録・LISの復元は $O(N)$ でできるので、計算量は変わらず $O(N \log{N})$ となる。

条件として、「部分列として同じであっても取り出した位置が異なる場合は別カウント」とする。

セグメント木を使う方法を拡張する。

• $DP[i]=a_i$ を末尾に必ず使用するような増加部分列の中で、(最長のものの長さ, その個数)

セグメント木なら、これは適切にマージできる。（長さが同じなら個数を合算し、どちらかが大きいならそちらを継承する）

$a_i$ について処理する際、$[0,i)$ の区間を求め、(最長の長さ+1, 個数) が $DP[i]$ となる。

計算量のオーダーは $O(N \log{N})$ となる。

2つの文字列 $S,T$ がある時、「$S$ の部分列でもあり、$T$ の部分列でもある」文字列を共通文字列という。

そのうち最長のものを最長共通部分列（Longest Common Subsequence）という。

文字列 $S,T$ が与えられたとき、2つの最長共通部分列の長さを求めましょう、という問題。

以下のDPを考える。

• $\mathrm{DP}[i,j]:=S[:i]$ と $T[:j]$ の最長共通部分列の長さ
  • ただし $S[:i]$ は $S$ の先頭 $i$ 文字を指す

$\mathrm{DP}[i,j]$ を求めるには、

• $S_i=T_j$ の時
  • $\mathrm{DP}[i-1,j-1]$ で作られる共通部分列の末尾に1文字追加できる。$\mathrm{DP}[i-1,j-1]+1$
• $S_i \neq T_j$ の時
  • どちらかを1文字削ったものと同じとなる。\max(\mathrm{DP}[i-1,j],\mathrm{DP}[i,j-1])$

$\mathrm{DP}[i,j]$ を埋めるには、$\mathrm{DP}[i-1,j-1],\mathrm{DP}[i-1,j],\mathrm{DP}[i,j-1]$ が埋まっている必要がある。
$\mathrm{DP}[0,*]$ と $\mathrm{DP}[*,0]$ は $0$ 確定なので埋めておき、 あとは 'for i in (1,…,|S|) for j in (1,…,|T|)' の2重ループで処理すればよい。

$\mathrm{DP}[|S|,|T|]$ が最長共通部分列の長さとなる。
計算量は $O(|S||T|)$。

S = XMJYAUZ
T = MZJAWXU

      0 1 2 3 4 5 6 7
        M Z J A W X U
0   | 0 0 0 0 0 0 0 0
1 X | 0 0 0 0 0 0 1 1
2 M | 0 1 1 1 1 1 1 1
3 J | 0 1 1 2 2 2 2 2
4 Y | 0 1 1 2 2 2 2 2
5 A | 0 1 1 2 3 3 3 3
6 U | 0 1 1 2 3 3 3 4
7 Z | 0 1 2 2 3 3 3 4

DPの持たせ方を変えた別解法

• Longest_common_subsequence_problem

長さを求める際のDPの結果から、具体的な最長共通部分列の1例を復元できる。

DPテーブルから逆向きに復元する。$(i,j)=(|S|,|T|)$ で初期化する。
また、復元結果を記録する配列 $U$ を空で初期化する。

同じである数字の方に $(i,j)$ を移動する。両方同じ場合は適当に1つ選んで移動する。

$S_i=T_j$ となっている。$U$ にその文字を加え、$(i-1,j-1)$ に移動する。

$\mathrm{DP}[i,j]=0$ になったら終了。
$U$ をひっくり返すと、最長共通部分列となる。

      0 1 2 3 4 5 6 7
        M Z J A W X U
0   | 0 0 0 0 0 0 0 0
1 X |⓪ 0 0 0 0 0 1 1
2 M | 0❶① 1 1 1 1 1
3 J | 0 1 1❷ 2 2 2 2
4 Y | 0 1 1② 2 2 2 2
5 A | 0 1 1 2❸③③ 3
6 U | 0 1 1 2 3 3 3❹  丸付きの数字を辿っていき、
7 Z | 0 1 2 2 3 3 3④  黒丸の数字を拾っていくと、LCS（の1つ）は MJAU と復元できる

$S,T$ いずれか一方に出てくる文字が全て異なることが分かっていれば、より少ない計算量で求められる。
ここでは $S$ の文字が全て異なるとする。

$S$ に出てくる順に、文字を数値に置き換える。$T$ もその置換に従って置き換える。$S$ に出てこない文字は取り除く。

S =  B R O W N C A T
      ↓
S'=  1 2 3 4 5 6 7 8

T =  W H I T E C O W
      ↓
T'=  4 x x 8 x 6 3 4    Sに出てこない文字（x）は、取り除く

最長共通部分列の長さは、$T'$ の最長増加部分列の長さとなり、$O(|S|+|T| \log{|T|})$ で求められる。

「共通部分列として同じであっても、$S,T$ から取り出した位置が異なる場合は別カウント」の場合の個数を数える。

• AtCoder ABC 130 E - Common Subsequence (青色, 500 点) - けんちょんの競プロ精進記録
  • ※上記記事は、最長とは限らない「共通部分列」の数え上げだが、参考として。

長さを求めるものとは別に、個数を数えるDP配列を用意する。

• $\mathrm{DP}_l[i,j]:=S[:i]$ と $T[:j]$ から作られる最長共通部分列の長さ
• $\mathrm{DP}_c[i,j]:=S[:i]$ と $T[:j]$ から作られる最長共通部分列の個数

$\mathrm{DP}_c[0,*]=\mathrm{DP}_c[*,0]=1$、他は $0$ で初期化する。

遷移では、以下のようにすればよい。$\mathrm{DP}_c[i,j]$ を求める。$(1 \le i \le |S|,1 \le j \le |T|)$

• まずは $DP_l[i,j]$ を通常の手順で更新する。
• 次の各条件を調べ、$DP_c[i,j]$ を更新する。
  • $S_i=T_j$ なら、$\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j-1]$
  • $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i,j-1]$ なら、$\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i,j-1]$
  • $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j]$ なら、$\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j]$
  • $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j-1]$ なら、$\mathrm{DP}_c[i,j]-=\mathrm{DP}_c[i-1,j-1]$

4つめの更新で減算しているのは、$\mathrm{DP}_c[i-1,j-1]$ で数えられている最長共通部分列が 「→↓」と「↓→」の2通りの経路で重複して $\mathrm{DP}_c[i,j]$ に足し込まれるのを防ぐためである。

「$S,T$ から取り出した位置が異なっても、文字列として同じ場合は1カウント」の場合の個数を数える。

上記の4種類のDP遷移のうち、下3つを、$S_i=T_j$ である場合は行わないようにすればよい。つまり、

• $S_i=T_j$ なら、$\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j-1]$
• $S_i \neq T_j$ かつ、
  • $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i,j-1]$ なら、$\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i,j-1]$
  • $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j]$ なら、$\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j]$
  • $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j-1]$ なら、$\mathrm{DP}_c[i,j]-=\mathrm{DP}_c[i-1,j-1]$

でよい（未検証）

お気持ち

DP_lの結果に対し、同じ文字が交差する箇所に [ ] を付けたもの

      a   c   b   a   b   c   a
   0  0   0   0   0   0   0   0
a  0 [1]  1   1  [1]  1   1  [1]
b  0  1   1  [2]  2  [2]  2   2
c  0  1  [2]  2   2   2  [3]  3
a  0 [1]  2   2  [3]  3   3  [4]
c  0  1  [2]  2   3   3  [4]  4
b  0  1   2  [3]  3  [4]  4   4
a  0 [1]  2   3  [4]  4   4  [5]
a  0 [1]  2   3  [4]  4   4  [5]

      a   c   b   a   b   c   a
   0→0→ 0→ 0→ 0→ 0→ 0→ 0
   v↘         ↘          ↘
a  0 [1]→1→ 1✖[1]→1→ 1✖[1]    ✖: 遷移しないことで重複を防いでいる箇所
   v  v    ↘       ↘
b  0  1→ 1  [2]→2✖[2]→2→ 2
   v  v↘     v         ↘
c  0  1  [2]→2→ 2→ 2  [3]→3
   v↘✖  v    ↘           ↘
a  0 [1]  2→ 2  [3]→3→ 3  [4]
: