クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-3 最長増加部分列問題」(p.63)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 最長増加部分列問題」(p.63)
のコードをPythonで書き直したものとなっています。

入力

n\\a_1\,…\,a_n

入力例



5
4 2 3 1 5


解答

O(n^2)の解法

MAX_N = 1000

# 入力
n = int(input())
a = list(map(int,input().split()))

dp = [0] * MAX_N    # DPテーブル
res = 0
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
        res = max(res, dp[i])
print(res)

O(n log n)の解法

MAX_N = 1000
INF = float('inf')

# 二分探索するためにbisect_left関数をインポートする
from bisect import bisect_left

# 入力
n = int(input())
a = list(map(int,input().split()))

dp = [INF] * MAX_N    # DPテーブル

for i in range(n):
    dp[bisect_left(dp, a[i])] = a[i]
print(bisect_left(dp, INF))