입력 | 출력 |
---|---|
6 10 20 10 30 20 50 | 4 10 20 30 50 |
: 가장 긴 증가하는 부분 수열을 구하기 위해 가장 긴 증가하는 부분 수열의 길이가 k일 때 i를 1부터 k까지 키워나가며 해당 dp테이블의 인덱스에 대한 수열의 값을 출력하려고 하였다. --> 틀렸습니다.
- 인덱스로 접근. max(dp)의 인덱스에서 시작해서 거꾸로 0까지.
- 바로 전 수의 dp값 + 1 == 해당 수의 dp값
n = int(input())
nums = list(map(int, input().split()))
dp = [1]*n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
k = max(dp)
print(k)
idx = dp.index(k)
arr = [nums[idx]]
for i in range(idx, -1, -1):
if dp[i]+1 == k:
k = dp[i]
arr.append(nums[i])
arr.reverse()
print(*ans)