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

https://www.acmicpc.net/problem/17216

 

n = int(input())
arr = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[0] = arr[0] 

# arr = 9 2 1 100 22
# dp  = 9 11 12  100 122
for i in range(1, n):
    dp[i] =arr[i] 
    cnt = 0 
    for j in range(i-1 , -1,-1):
        if arr[i] < arr[j] :
            cnt +=  1 
            dp[i] = max(dp[j] + arr[i],dp[i])
print(max(dp))