https://www.acmicpc.net/problem/11053
수열의 요소를 골라서 가장 긴 부분 수열을 만든 뒤, 그 수열의 길이를 출력하면 된다.
dp[i]
= 수열의 i번째 요소까지 만들 수 있는 가장 긴 배열의 길이 ( i >= 1 )
dp = [1] * n
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j]+1)
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int,input().rsplit()))
dp = [1] * n
# i = 0, j = 0
# i = 1, j = 0, 1
# i = 2, j = 0, 1, 2 ...
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j]+1)
print(dp)