백준 14003 - 가장 긴 증가하는 부분 수열 5 (파이썬)

Answer

from sys import stdin

input = stdin.readline

N = int(input())
a = list(map(int, input().split()))
dp = [0] * N
tmp = []
answer = 0

def binary_search(start, end, num):
    while start < end:
        mid = (start + end) // 2

        if tmp[mid] < num:
            start = mid + 1
        else:
            end = mid
            
    return end

for i in range(N):
    if not tmp or tmp[-1] < a[i]:
        tmp.append(a[i])
        dp[i] = len(tmp) - 1
        answer = dp[i]
    else:
        dp[i] = binary_search(0, len(tmp) - 1, a[i])
        tmp[dp[i]] = a[i]

print(answer + 1)
res = []

for i in range(N - 1, -1, -1):
    if dp[i] == answer:
        res.append(a[i])
        answer -= 1

print(*res[::-1])