[백준][Python] 17216 가장 큰 감소 부분 수열

결과를 누적시켜주며 끝까지 간다

 

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
dp = arr[:]

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