이 문제는 계속 반복적으로 나오는 가장 긴 증가하는 수열 찾기 문제이다. 동적 프로그래밍 방식으로 풀어보자.
먼저 앞에서부터 각 위치까지의 가장 긴 증가하는 수열을 저장하고자 dp에 길이와 수열을 저장하는 이중 리스트로 만들었다.
앞에서부터 각 위치까지 앞에 작은 수가 있고, 수열 길이가 길다면 업데이트하게끔 했고, 만약 업데이트가 한번도 안 되었다면 == 내가 가장 작은 수라면 나 자신을 갖는 수열로 해주었다.
마지막 수열 길이를 기준으로 내림차순 정렬을 해주어 맨 앞에 있는 수열을 찾아 출력하였다.
import sys
input = sys.stdin.readline
def solve():
global n, arr
dp = [[0, []] for _ in range(n)]
dp[0][0] = 1
dp[0][1] = [arr[0]]
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j]:
if dp[j][0] + 1 > dp[i][0]:
dp[i][0] = dp[j][0] + 1
dp[i][1] = dp[j][1] + [arr[i]]
if dp[i][0] == 0:
dp[i][0] = 1
dp[i][1] = [arr[i]]
dp.sort(reverse = True)
print(dp[0][0])
for i in dp[0][1]:
print(i, end = ' ')
n = int(input())
arr = list(map(int, input().split(' ')))
solve()