DP
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = [1] * (n+1)
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
Python
복사
이진 탐색
import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
arr = []
for x in a:
pos = bisect.bisect_left(arr, x)
if pos == len(arr):
arr.append(x)
else:
arr[pos] = x
print(len(arr))
Python
복사