LIS - 최장 증가 부분수열

핵심포인트

부분수열 중 증가하는 가장 긴 "길이"를 찾는 것이 LIS의 목표.
n개의 배열을 한번씩만 방문하면서 현재 값이 들어갈 위치를 이진탐색O(log n)으로 빠르게 찾는다.

실습

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

import sys
input = sys.stdin.readline
        
n = int(input())
a = [*map(int, input().split())]
l = [a[0]]

def bst():
    s,e = 0,len(l)
    while s < e:
        mid = (s + e) // 2
        if i == l[mid]:
            return mid
        if i > l[mid]:
            s = mid + 1
        else:
            e = mid
    return s

for i in a:
    if l[-1] < i:
        l.append(i)
    else:
        pos = bst()
        l[pos] = i
print(len(l))