LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) - 징검다리 문제

풀이: LIS의 길이만 필요하기 때문에 더 작은 수로 이어지는 LIS 후보를 만들어 앞으로 올 수 있는 수들의 여지를 넓힌다.
최종 lis 배열의 길이가 lis의 길이가 된다.

import sys
from bisect import bisect_left

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

lis = []
for elem in arr:
    pos = bisect_left(lis, elem)
    if pos == len(lis): # elem이 현재 lis의 끝보다 크다면
        lis.append(elem) # 새로운 원소 추가 (LIS 길이 증가)
    else: # elem이 이미 있는 값보다 작거나 같다면
        lis[pos] = elem # 해당 위치를 대체하여 더 나은 LIS 후보를 만듦

print(len(lis))