[BOJ] 11053 - 가장 긴 증가하는 부분 수열

풀이

data	10	20	10	30	20	50
dp	1	2	1	3	2	4

dp 문제입니다. data 변수에는 입력값을, dp 변수에는 현재 위치에서 최대 길이를 저장합니다.

dp변수는 기본적으로 자신의 길이 1을 가지므로 1로 초기화 해줍니다.

 

dp 변수에는 현재 데이터보다 값이 작은 이전 데이터들 중에서 최대 dp값에 1을 더하여 저장합니다.

출력 시에는 dp의 마지막 원소가 최댓값이라는 보장이 없기 때문에 dp에서 최댓값을 뽑아 출력합니다.

 

Python3 Code 

import sys 

n = int(input())
data = list(map(int, input().split()))

dp = [1] * n

for i in range(1, n):
    max_dp = 0

    for j in range(0, i):
        if max_dp < dp[j] and data[i] > data[j]:
            max_dp = dp[j]
    
    dp[i] = max_dp + 1
    
print(max(dp))