[백준14002] 가장 긴 증가하는 부분수열 4

문제

---

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

14002번: 가장 긴 증가하는 부분 수열 4

 

생각의 흐름

---

이전에 포스팅한 적이 있는 가장 긴 감소하는 수열과 유사하다. 차이점은 길이 뿐 아니라 수열까지도 출력한다는 것인데 이 때 뒤에서부터 순차적으로 출력해야한다는 것만 유념하면 된다.

 

코드

---

# 백준 14002
N = int(input())
arr = list(map(int, input().split()))
dp = [1]*N

for i in range(1, N):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))
order = max(dp)
lst = []
for i in range(N-1, -1, -1):
    if dp[i]==order:
        lst.append(arr[i])
        order-=1
lst.reverse()
for i in lst:
    print(i, end=' ')