1. 문제 설명

가장 긴 증가하는 부분 수열

2. 문제 분석

dp를 통해 "가장 큰" 수 자리 인덱스를 고정, 이 수보다 작은 수를 앞 인덱스에서부터 검사하면서 가장 큰 합이 되는 지점을 dp에 기록한다.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
dp = numbers[:]
for i in range(n):
    # i번째 수 고정, 이 수보다 작은 앞의 j 수 합계 구하기
    for j in range(i):
        if numbers[j] < numbers[i]:
            dp[i] = max(dp[i], dp[j] + numbers[i])

print(max(dp))