[백준 11055] 가장 큰 증가 부분 수열 (Silver 2)

문제

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

접근

1. 이중 포문을 이용해 첫 번째 포문에서는 타겟이 되는 인덱스 (i)를 지정한다.
2. 두 번째 포문에서는 현재 가르키고 있는 곳의 값이 i의 값보다 작으면, j의 최적해 + j가 가르키고 있는 값과 i의 최적해와 비교해 더 큰 값을 i의 최적해로 둔다.

Code

import sys

n = int(sys.stdin.readline())
arrs = list(map(int, sys.stdin.readline().split()))
dp = [0]*n

for i in range(n):
    dp[i] = arrs[i]
    for j in range(i):
        if arrs[j] < arrs[i]:
            dp[i] = max(dp[j] + arrs[i], dp[i])
print(max(dp))

여담

동적 계획법은 실버도 어려운 것 같다. 수학적 지식이 좀 필요한 영역 같음 ㅠ