[백준/DP] 11053: 가장 긴 증가하는 부분 - 파이썬

문제

https://www.acmicpc.net/problem/11053

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

 

풀이

LIS 라는 DP문제이다.

(LIS 알고리즘에 대한 내용은 추후 블로그에 업로드 예정)

dp리스트에 현재 자신 숫자를 포함해 만들 수 있는 부분 수열 크기를 저장한다.

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

 

n = int(input())
numList = list(map(int, input().split()))
lenNum = len(numList)

dp = [1] * lenNum

for i in range(lenNum):
    for j in range(i):
        if numList[j] < numList[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))