[백준 12738번] 가장 긴 증가하는 부분 수열 3 (python, bisect)

www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

1과 다른 점은 배열 원소의 최소값이 -10^9이기 때문이다. 

따라서 q의 처음 최소값을 그 수보다 작은 수로 하면 된다

 

import sys
from bisect import bisect_left
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))


#마지막 길이 출력 때 1을 빼준다
q=[-1000000001]
for x in arr:
    if q[-1]<x:
        q.append(x)
    else:
        #bisect_left는 원소가 들어갈 위치를 반환해준다
        #길이를 구하는 문제에만 해당된다
        q[bisect_left(q,x)]=x
# print(q)
print(len(q)-1)