12015: 가장 긴 증가하는 부분 수열 2

문제 링크

12015: 가장 긴 증가하는 부분 수열 2

구현 방식

• 이분 탐색을 이용해서 O(nlogn)으로 LIS의 길이를 구해줄 수 있다 (LIS의 구성 요소는 다를 수 있음)

코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().strip().split()))

LIS = [-1]
for a in A:
    if LIS[-1] < a:
        LIS.append(a)
    else: #이분 탐색을 통해 a가 들어갈 위치를 찾음
        left = 0
        right = len(LIS)

        while left < right:
            mid = (left+right)//2
            if LIS[mid] < a: left = mid+1
            else: right = mid
        LIS[right] = a
print(len(LIS)-1)