[백준_17216] 가장 큰 감소하는 부분수열 python

이런 류의 문제에 이젠 익숙해진 기분이다.

마찬가지로 n의 범위가 1000이하이니

n^2까지의 시간복잡도는 인정해준다.

# n 입력
n = int(input())

# a 입력
a = list(map(int, input().split()))

# dp 설계
dp = [
    0 for _ in range(n)
]

# dp 초기설정
dp[0] = a[0]

# dp 채워넣기
for i in range(1, n):
    
    # 최댓값 설정
    M = 0

    # 이전까지 돌면서
    for j in range(i):
        # 감소하는 수열 중 dp값이 가장 큰 것을 찾아
        if a[j] > a[i] and dp[j] > M:
            # 최댓값 갱신
            M = dp[j]
    
    # dp 넣어주기
    dp[i] = M + a[i]

# 출력
print(max(dp))