[Code Tree] 최대 감소 부분 수열 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-decreasing-subsequence/description

최대 감소 부분 수열 설명 | 코드트리

 

---

풀이

문제 요약

주어진 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하자.

아이디어

점화식은 다음과 같다.

dp[i] : i번째 요소로 끝나는 LDS의 최대 길이

LIS의 응용문제다. 부등호만 바꾸면 된다.

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

# Please write your code here.

dp = [1] * n

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

print(max(dp))

풀이시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/14 최대 감소 부분 수열(challenge-longest-decreasing-subsequence).py

problem-solving/code-tree/Algorithm Intro/DP I/14 최대 감소 부분 수열(challenge-longest-decreasing-subsequence).py at ma