[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)

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

 

LIS

Longest Increasing Subsequence

 

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

d = [0]

for i in arr:
    if d[-1]<i:
        d.append(i)
    else:
        left = 0
        right = len(d)

        while left<right:
            mid = (right+left)//2
            if d[mid]<i:
                left = mid+1
            else:
                right = mid
        d[right] = i

print(len(d)-1)

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
d = []
for i in arr:
    k = bisect_left(d, i)
    if len(d) == k:
        d+=[i]
    else:
        d[k] = i

print(len(d))