[BOJ] 가장 긴 감소하는 부분수열

---

코드

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
d = [1]*n

for i in range(n):
    for j in range(i, -1, -1):
        if a[i] < a[j] and d[i] <= d[j]:
            d[i] = d[j] + 1
            
print(max(d))

결과

풀이 방법

• 각 인덱스에 대해 '현재 인덱스까지의 가장 긴 감소하는 부분수열 길이'를 배열 d에 저장한다.
• 현재 인덱스 이전의 수열에서 현재 인덱스의 수보다 큰 수를 찾고, 해당 수의 인덱스까지의 d값들 중 가장 큰 값 + 1 을 현재 인덱스의 d값으로 저장한다.
• 배열 d의 값 중 최대값이 가장 긴 감소하는 부분수열의 길이이다.

---