[백준] 14002 : 가장 긴 증가하는 부분수열 - Python(파이썬)

문제

www.acmicpc.net/problem/14002

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

풀이

• 동적 계획법
• 길이 : 일차원 배열에 당시 길이 최대값 유지/갱신 : 이전 수+1 
• 수열 출력 : 배열에 최대값 가진 인덱스부터 -1 하며 원래 수열에서 해당 값 가져오기

코드

n = int(input())
arr = list(map(int, input().split()))
max_len = [1]*n

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

print(max(max_len))
curr_max = max(max_len)
lst = []
for i in range(n-1, -1, -1):
    if max_len[i]==curr_max:
        lst.append(arr[i])
        curr_max-=1
lst.reverse()
for i in lst:
    print(i, end=' ')