最長増加部分列 (Longest Increasing Subsequence, LIS)

概要

以下のような問題

  • 長さ \(N\) の数列がある

  • \(a_{i_1} < a_{i_2} < ... < a_{i_k}\) となる \(i_1 < i_2 < ... < i_k\) の中で \(k\) の最大値を求める

以下のようなDPを考える。

  • \(dp[k] :=\) 長さkとなるLISの中で、列最後の要素の最小値

そして \(dp[j] < a_i\) となる最大のjを二分探索で見つけ、 \(dp[j+1] = \min(a_i, dp[j+1])\) で更新していく。

計算量

\(O(N \log N)\)

実装

from bisect import bisect

# N: 数列の長さ
# A[i]: a_i の値
def solve(N, A):
    INF = 10**10

    dp = [INF]*(N+1)
    dp[0] = -1
    for a in A:
        idx = bisect(dp, a-1)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

Verified

  • AOJ: "DPL_1_D: Combinatorial - Longest Increasing Subsequence": source (Python3, 0.12sec)

戻る