99클럽 코테 스터디 28일차 TIL + DP

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

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

dp = [0] * n
dp[0] = A[0]

for i in range(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))

• dp리스트를 0으로 초기화 한 후 dp[0]값은 이전 값과 비교할 것이 없기 때문에 A[0]으로 초기화 해준다.
• 자신 앞까지의 값을 비교하며 이전까지의 증가하는 값의 합과 자기자신의 값(dp[j]+A[i])과 dp[i]중 큰 값으로 초기화한다.
• 자신보다 큰 값을 만나면 A[i]과 dp[i] 중 큰 값으로 초기화 해주어야 하는데 증가하는 부분 수열이 없는 경우 자기자신의 값으로 초기화 해 뒤에 나올 값들에 대비해야한다.