백준 11053번 파이썬

 

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

가장 긴 증가 부분 수열을 찾는 것으로,

각 수열 요소보다 작은 요소들의 수열 길이 중 가장 큰 것 +1 을 하는 방식으로 문제를 풀 수 있다.

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

주어진 수열에서 증가수열 & 수열의 길이가 최대가 되어야한다.

그렇다면 dp를 이용해서 현재까지 가장 수열의 길이가 큰 것을 차근차근 구하고, 이를 배열에 저장한다. 현재 요소보다 작은 수들의 수열길이 중 최대 수열의 길이 +1 을 하는 방식으로 문제를 풀 수 있다.

n = int(input())

arr = list(map(int,input().split()))
dp = [0] * n
length = -1
dp[0] = 1

for i in range(1, n):
    for k in range(i):
        if arr[i] > arr[k]:
            if dp[k] > dp[i]:
                dp[i] = dp[k]
    dp[i] += 1
print(max(dp))