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

문제

N과 수열이 주어질 때 부분 수열 중에서 가장 합이 큰 것을 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/11055)

풀이

전에 풀었던 가장 긴 증가 부분 수열(https://kswims.tistory.com/152) 문제와 거의 비슷합니다. 이전 문제는 길이를 구해야했다면 이번엔 합으로 dp배열을 추가해나갑니다. i번째 값이 들어왔을 때 i-1번째부터 쭉 내려가며 i번째 값보다 작은 숫자이면서 dp의 값을 가장 큰 값을 택해서 dp[i] = 해당값+num[i]를 해주면 됩니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/11055.cpp