[백준-11055] 가장 큰 증가 부분 수열

---

나의 코드

import sys
input = sys.stdin.readline

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

dp=[0]*n #합
dp[0]=a[0]
mx=a[0]
for i in range(1,n):
    for j in range(i):
        if a[j]<a[i] and dp[j]>dp[i]:
            dp[i]=dp[j]
    dp[i]+=a[i]
    mx = max(mx,dp[i])

print(mx)

---

풀이

처음엔 dp를 [수열의합, 수열의 가장큰수]로 이중리스트로 관리하였지만 생각해보니 수열의 가장 큰수는 항상 해당 인덱스의 a값으로 필요가없다는걸 깨달았다. 그래서 일반리스트로 증가수열중 가장 큰값을 저장하도록 하였다.
dp[i]는 dp[0]~dp[i-1]까지 값중 증가수열을 만족하는 값중 가장 큰값에 a[i]를 더한값이다.