Baekjoon 12015. 가장 긴 증가하는 부분 수열 2 / Python

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

• LIS (Longest Increasing Subsequence) 문제를 이분 탐색을 활용하여 O(n log n) 의 시간복잡도로 구현하는 문제

import sys
input = sys.stdin.readline

def sol(arr, num):
    l, r = 0, len(arr) - 1
    while l <= r:
        m = (l + r) // 2
        if arr[m] >= num:
            r = m - 1
        else:
            l = m + 1
    return l

def longest_increasing_subsequence(n, arr):
    res = []
    for i in arr:
        pos = sol(res, i)
        if pos == len(res):
            res.append(i)
        else:
            res[pos] = i
    return len(res)


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


print(longest_increasing_subsequence(n, arr))