1. 문제 설명

가장 긴 증가하는 부분 수열 4

2. 문제 분석

가장 긴 증가한느 부분 수열을 통해 길이를 카운트, dp에 해당 dp의 길이를 기록하자. 거꾸로 거슬러 올라가면 스택에 해당 dp에 처음 나온 인덱스를 numbers에서 꺼내 기록한다.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [1 for i in range(n)]
answer = []
for i in range(n):
    # i번째 수 고정, 이 수보다 작은 앞의 j 수 합계 구하기
    for j in range(i):
        if numbers[j] < numbers[i]:
            dp[i] = max(dp[i], dp[j] + 1)

length = max(dp)
result = []

for idx in range(n-1, -1, -1):
    if length == dp[idx]:
        result.append(numbers[idx])
        length -= 1

result.reverse()
print(len(result))
print(*result)