문제

[백준] 가장 긴 증가하는 부분 수열 3 (Gold 2)

요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라. 단, A의 크기 N은 1보다 크고 1,000,000보다 작고, A(i)는 -1,000,000,000보다 크고 1,000,000,000보다 작다.

분류

  • 다이나믹 프로그래밍

풀이

1. 내 풀이 (DP)

N의 크기가 크기 때문에 O(NlogN)에 해결해야 한다. 또, 음수가 들어갈 수 있기 때문에 초깃값 설정에 유의하자.


from bisect import bisect_left as bl

n = int(input())
arr = [0] + list(map(int, input().split()))

dp = [0] * (n + 1)
d = [-1000000001]

for i in range(1, n + 1):
    idx = bl(d, arr[i])
    if idx == len(d):
        d.append(arr[i])
        dp[i] = idx
    else:
        d[idx] = min(d[idx], arr[i])
        dp[i] = idx

print(len(d) - 1)