[BOJ] (DP) 11055번 가장 큰 증가하는 부분수열

i를 1씩 늘려가면서, 자신보다 왼쪽에 있으면서 작은 수들만 골라 다 더하고, 

만들어진 dp배열에서 가장 큰 값을 구하면 된다

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().rstrip().split()))
dp = [a for a in 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))

 

 

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

11055번: 가장 큰 증가 부분 수열