📖Problem

11055번: 가장 큰 증가하는 부분 수열

🔍Intuition

지난번 #11053. 가장 긴 증가하는 부분수열 문제의 시리즈 문제에 접근해보려고 한다. 지난번 #11053다음 단계인 #11055번. 가장 큰 증가하는 부분 수열의 문제는 아래와 같다.

Untitled

Untitled

처음에는 오잉 가장 큰 수열하려면 전부 다 더하면 되지 않을까?! 했는데, 그게 아니었다.

조건은 2가지인것.

  1. 증가하는 수열이어야 한다.
  2. 증가하는 수열 내의 합이 가장 큰 수열이어야 한다.

이전에 #11053은 DP 테이블에 가장 “긴” 증가하는 수열의 길이를 저장하는 반면에, 이번 #11055 에서는 DP테이블에 증가하는 수열 중에서 가장 합이 “큰” 수열의 합이 저장되어야 한다. -

따라서 증가하는 수열의 코드를 기반으로 한다.(놀랍게도 일주일전에 풀었는데 기억 안 남;;😓)

🔍Approach

이 방식으로 접근할 경우 dp에는 아래와 같이 저장되게 된다.(예시 기준)

print(nums)
# 1 100 2 50 60 3 5 6 7 8

print(dp)
# [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]
i 0 1 2 3 4 5 6 7 8 9
nums[i] 1 100 2 50 60 3 5 6 7 8
dp[i] 1 101 3 53 113 6 11 17 24 32