11055 가장 큰 증가 부분 수열

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

dp = [x for x in arr]
dp_sum = 0

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

로직 구현 순서

11053번과 굉장히 유사하다. 다른점은 이 문제에서는 증가하는 수의 개수를 카운트하는것이 아니고 증가하는 수를 누적해서 더한값을 구하라는 문제이다.

그렇기 위해서는 수의 값들을 누적해서 구하면된다.

dp를 초기화 할때 1이 아닌 입력받은 수들로 초기화 해준다

dp = [x for x in arr]

1, 2의 수를 가지고 있는 경우 dp[1] = 2의 값과 dp[0] = 1의 값을 비교한 후 dp[1]의 값이 더 큰 경우 증가하고 있기 때문에 dp[1] = 2 와 dp[0] = 1 + 2를 더한 값 중 max값을 찾아 dp[1]의 값을 업데이트 시켜주면 된다.

dp[i] = max(dp[i], dp[j] + arr[i])