[백준/Python] 11055 - 가장 큰 증가하는 부분수열

문제

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

풀이
완전탐색식으로 for를 이중으로 쓰면 될 것 같은데..? 라고 생각했다가 그래도 dp문제니까 for 하나만 쓰고 풀 수 있지 않을까 생각했다
다른 풀이들을 보니 이중 for를 썼다 ..

A의 원소들을 처음부터 순회하되 현재 가리키고 있는 원소가 수열의 마지막 원소라고 가정하게 된다
그리고 현재 원소보다 이전에 나타난 값들을 비교해준다
만약 이전에 나타난 원소들 중 현재원소보다 작은 원소가 있다면 그 원소까지의 가장 큰 부분 수열의 합에 현재 원소를 더한것과 현재 원소까지의 가장 큰 부분 수열의 합을 비교해 더 큰 것을 선택한다
만약 이전에 나타난 원소들 중 현재원소보다 큰 원소가 있는 경우 현재 원소까지의 가장 큰 부분 수열의 합과 현재 원소 값을 비교해 더 큰 것을 선택한다

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

dp = [0]*n
dp[0] = a[0]

for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j]+a[i])
        else:
            dp[i] = max(dp[i], a[i])
print(max(dp))