[백준] 11053번: 가장 긴 증가하는 부분 수열 - python

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

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

 

DP문제로 연속합과 비슷하게 가장 길게 증가하는 부분의 길이를 dp로 저장해 풀어나가는 방식이다.

 

DP에 저장하기까지 생각이 꽤 오래걸렸다. 공부를 더 해야겠다.

n = int(input())

arr = list(map(int, input().split()))


dp = [1] * (n+1)

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

 

완성