最長増加部分列(LIS)

最長増加部分列 (Spaghetti Source)

最長増加部分列

最長増加部分列 (Longest Increasing Subsequence, LIS) は、数列の部分列として作ることができる単調増加部分列のうち、最も長いのものをいう。

例えば数列 \(\{a_i\}\)

\[2, 3, 1, 7, 5, 2, 3, 0, 5\]

に対して、その最長増加部分列は

\[1, 2, 3, 5\]

となる。

実装

動的計画法と二分探索を用いて、最長増加部分列の長さを計算量 \(\mathcal{O}(n\log{n})\) で求めることができる。

\(dp[i]:\) 長さ \(i\) の単調増加部分列の右端の数字のうち、最小の値

from bisect import bisect_left

def lis_length(A, INF=10**9):
    dp = [INF for _ in A]
    for a in A:
        idx = bisect_left(dp, a)
        dp[idx] = a
    return bisect_left(dp, INF)

A = [2, 3, 1, 7, 5, 2, 3, 0, 5]
print(lis_length(A))

4

最長増加部分列そのものを求めるには、DPの更新時に更新箇所のインデックスも一緒にメモしておけばよい。

from bisect import bisect_left

def LIS(A, INF=10**9):
    dp = [INF for _ in A]
    b = [-1 for _ in A]
    for i in range(len(A)):
        idx = bisect_left(dp, A[i])
        dp[idx] = A[i]
        b[i] = idx + 1
    l = bisect_left(dp, INF)
    seq = [0 for i in range(l)]
    for i in range(len(A)-1, -1, -1):
        if b[i] == l:
            l -= 1
            seq[l] = A[i]
    return seq

print(LIS(A))

[1, 2, 3, 5]