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

문제

www.acmicpc.net/problem/12015

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

 

풀이 및 소스코드

jainn.tistory.com/90

최장 증가 부분 수열(LIS) 알고리즘

이걸 보고 오면 금방 풀린다.

import sys
input = sys.stdin.readline

n = int(input())
cases = list(map(int, input().split()))
lis = [0]

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

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

print(len(lis)-1)