[BOJ] (ALGO) 14003번 가장 긴 증가하는 부분 수열 5 ★

 

LIS 알고리즘을 이용.

LIS배열 자체가 아닌 LIS의 길이를 구하는 알고리즘에서 응용을 해야한다.

LIS에 관한 내용은 알고리즘 카테고리에 다음에 포스트할 예정.

 

from bisect import bisect_left

n = int(input())
arr = list(map(int, input().split()))
lis = []
insert_pos = []

for i in range(n):
    if i==0:
        lis.append(arr[i])
        insert_pos.append(i)        
        continue
        
        
    if lis[-1] < arr[i]:
        insert_pos.append(len(lis))
        lis.append(arr[i])
        
    else:
        idx = bisect_left(lis, arr[i])
        insert_pos.append(idx)
        lis[idx] = arr[i]
        

ans = max(insert_pos)
print(ans+1)

lis = []
for i in range(n-1, -1, -1):
    if insert_pos[i] == ans:
        lis.append(arr[i])
        ans -= 1
        
while lis:
    print(lis.pop(), end=' ')

 

 

 

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5