[BOJ] 최장증가부분수열

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

나무위키

save[i] : 길이가 i인 부분수열들의 마지막 원소들 중 가장 작은 값을 저장한다.

import sys
input = sys.stdin.readline

n_arr = int(input())

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

save = [] # save[i] i개의 가장 긴 증가하는 부분수열을 가지는 arr[j] 값 중 최솟값
save.append(arr[0]) # arr의 첫번째 원소를 길이가 1인 부분수열로 추가해준다.

# save배열에서 target보다 작은 원소의 idx +1값을 이분탐색으로 찾아준다. 
# target보다 작은 원소의 LIS 길이 +1 이 target을 마지막으로 하는 LIS 길이이기 때문
# 작은 원소가 없는 경우 -1을 반환한다. 
def binarySearch(target): 
    left = 0
    right = len(save) - 1
    answer = 0
    while left <= right:
        mid = (left + right) //2
        if save[mid] < target:
            answer = mid + 1
            left = mid + 1
        else:
            right = mid - 1
    return answer

for i in range(1,len(arr)):
    idx = binarySearch(arr[i]) 
    if idx >= len(save): # target의 길이가 save보다 크면 save 맨 뒤에 추가한다
        save.append(arr[i])
    elif save[idx] > arr[i]: # target 값을 save[idx] 값으로 넣어준다 (target은 항상 save[idx] 값보다는 작을 것)
        save[idx] = arr[i]
    # print(save)
print(len(save))