[BOJ] [Python] 11053번 : 가장 긴 증가하는 부분 수열

간단한 예시

 

앞에서부터, 각 값에 해당하는 최대 수열 위치를 저장하면 된다.

 

 

예를 들어, 50의 위치 최댓값을 고려할 때

 

1. 30의 3번 뒤

2. 25의 6번 뒤

 

당연히 2번을 선택해야 한다.

둘 다 값이 50보다 작기 때문에, 더 큰 수열 위치를 선택한 것이다.

 

num = int(input())

li = list(map(int, input().split()))
dp = [0] * len(li)

for i in range(num):

    tmp = 0

    for j in range(i):
        if li[j] < li[i] and tmp < dp[j]:
            tmp = dp[j]
            dp[i] = tmp

    dp[i] += 1 # self

print(max(dp))