[백준 11722번] 가장 긴 감소하는 부분 수열 문제 풀이 with Python

 

< 문제 >

 

 

 

< 입출력 >

 

 

 

< 풀이 >

각 인덱스 별로 앞의 수보다 다음 수가 작을 경우 1씩 올려준다. 

dp를 이용하여 dp[i]에 인덱스 i까지 가장 긴 감소하는 부분 수열의 길이를 저장한다. 

 

 

 

 

< 코드 >

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

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