BOJ#11055 가장 큰 증가 부분 수열

BOJ#11055 가장 큰 증가 부분 수열

* 문제

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

* 풀이

BOJ#11053 문제와는 조금 다른 문제입니다.

11053 문제는 '증가하는 부분 수열' 중 가장 긴 수열의 길이를 구하는 것이었고,

11055 문제는 '증가하는 부분 수열' 중 수열의 합이 가장 큰 것을 구하는 것입니다.

즉, 가장 긴 수열이 항상 가장 큰 합을 보장하지 않으므로

dp를 11053 문제와는 다르게 설계하셔야 합니다.

11053의 dp[i]가 'A[i]를 포함하는 수열 중에, 길이가 가장 긴 수열의 길이' 였다면,

11055의 dp[i]는 'A[i]를 포함하는 수열 중에, 수열의 합이 가장 큰 수열의 합' 

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%2311055_SumOfLIS