[백준] 12015번 가장 긴 증가하는 부분수열2 - 이분탐색, LIS

https://www.acmicpc.net/problem/12015

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

 

LIS 알고리즘 정리

https://hhiyeon.tistory.com/167

[알고리즘] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

 

백준 풀이

#n = int(input())
#arr = list(map(int, input().split()))
n = 6
arr = [10, 20, 10, 30, 20, 50]
lis = [0]

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

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