풀이

가장 긴 증가하는 수열(LIS)는 기존풀이 방식(dp)과 이분탐색으로 풀어볼 수 있다.
문제와 같이 크기가 큰 수열은 시간초과가 뜨기 때문에 시간 복잡도가 O(nlog n)인 이분탐색을 사용해야한다.

import sys
import heapq
input = sys.stdin.readline

n = int(input())

A = list(map(int, input().split()))

d = [0]

for x in A:
    if d[-1] < x:
        d.append(x)
    else:
        start = 0
        end = len(d)

        while start < end:
            mid = (start + end) //2
            if d[mid] < x:
                start = mid + 1
            else:
                end = mid
        d[end] = x
print(len(d)-1)