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