[백준] 12015번 가장 긴 증가하는 부분 수열 2 (파이썬)

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

 

코드

import sys

def find(i):
    low, high = 1, len(stack)-1
    while low < high:
        mid = (low+high)//2
        if stack[mid] < i:
            low = mid +1
        elif stack[mid] > i:
            high = mid
        else:
            low = high = mid
    return high

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    li = list(map(int, sys.stdin.readline().split()))
    stack = [0]

    for i in li:
        if stack[-1] < i:
            stack.append(i)
        else:
            stack[find(i)] = i

    print(len(stack)-1)