[DP 알고리즘] 가장 큰 증가 부분 수열

기출: 백준 #11055

 

# d[n] = n번째 수를 선택한 경우의 최댓값

n = int(input())
arr = list(map(int,input().split()))
d = [-1 for _ in range(n)]

d[0] = arr[0]

for i in range(1, n):
    maxVal = arr[i]
    for j in range(i):
        if arr[j]<arr[i]:
            maxVal = max(maxVal, d[j]+arr[i])
    d[i] = maxVal

print(max(d))