[백준] 11055번(python 파이썬)

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

 

현재 값(A[i]에서 이전 값들(A[0] ~ A[i-1])을 보면서 현재값보다 작으면서 dp(이전에 구한값)값이 가장 큰 값을 찾는다.

 

n = int(input())
a = list(map(int, input().split()))
dp = [0] * n


def sequence():
    dp[0] = a[0]
    for i in range(1, n):
        max_value = 0
        for j in range(i):
            if a[i] > a[j]:
                if abs(a[i] - a[j]) != 0:
                    max_value = max(max_value, dp[j])

        max_index = dp.index(max_value)
        dp[i] = dp[max_index] + a[i]


sequence()
print(max(dp))