[백준] [이진 탐색] [최장증가수열] 12015. 가장 긴 증가하는 부분 수열 2

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

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

 

• 내 풀이
  • 최장증가수열
  • 노션 정리 참고할것

https://www.notion.so/0331-b6fec09feef240779bb8b7df87cb1947

from bisect import bisect_left

n=int(input())
graph=list(map(int,input().split()))
LIS=[graph[0]]


for i in range(n):
    if LIS[-1]>=graph[i]:
        idx=bisect_left(LIS, graph[i]) #위치 찾고
        LIS[idx]=graph[i] #값 업데이트

    else: #더 큰값나오면 추가: 길이 +1
        LIS.append(graph[i])

print(len(LIS))