最長増加部分列（LIS）

2022年7月18日

最長増加部分列とは

数列 {$ \small A_i$} が与えられたとき、並び順は変えずに {$ \small A_i $} の中からいくつかの要素を選んで作った数列を数列 {$ \small A_i$} の部分列といい、{$ \small A_i $} の部分列のうち、$ \small i<j$ ならば $ \small A_i < A_j$ がすべての $\small i < j$ に対して成り立つものを数列 {$ \small A_i$} の増加部分列という。数列 {$ \small A_i$} の増加部分列のうち長さが最長のものを最長増加部分列という。

最長増加部分列（LIS）の長さを求めるアルゴリズム

同じ長さの増加部分列ならば、最終要素が小さいほうがその後有利になる。長さに対する最小の最終要素をDPで計算する。

dp[i]: 長さが i+1 であるような増加部分列における最終要素の最小値（存在しない場合はINF）
初期値: dp[i] = INF
数列の要素 a[j] を前から見ていき、各 a[j] に対して i = 0 もしくは dp[i-1] < a[j] となる最大の i を見つけて dp[i] = a[j]
最終的に dp[i] がINFではない最大の i+1 がLISの長さとなる

コード例（Python）

長さ $ \small N $ の数列 $ \small A $ が与えられたときのLISを求めるプログラム。計算量は $ \small O(N\log{N}) $。

def solve(n, a):
    dp = [INFTY for _ in range(n)]
    ans = 0
    for i in range(n):
        ai = a[i]
        idx = bisect_left(dp, ai)
        if idx < n:
            dp[idx] = ai
            ans = max(ans, idx)
    return ans + 1