백준 11055 가장 큰 증가하는 부분 수열 / C++

문제 : 11055

풀이 point

가장 긴 증가하는 부분 수열과 비슷한 문제이다. 단 이번 문제는 가장 크게 증가할 때 그 합을 출력하는 문제이다.

dp배열을 입력받은 값들로 차례차례 채워준 후 가장 긴 증가하는 부분 수열을 풀 때와 똑같이 해준다.
단,

if(arr[i] > arr[j]) dp[i] = std::max(dp[i], dp[j]+arr[i]);

이 부분이 다르다. 원래는 + arr[i]를 해주는 것이 아닌 +1을 해주었다. 하지만 이 문제는 길이가 아닌 최대 값을 계산하는 것이기 때문에 arr[i]를 더해주어야한다.

코드

//백준 11055, 가장 큰 증가하는 부분 수열
#include <iostream>
#include <algorithm>

int arr[1'000];
int dp[1'000];

int main(){

    int N;
    std::cin >> N;

    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    std::copy(arr, arr+N, dp);
    
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<i; ++j){
            if(arr[i] > arr[j]) dp[i] = std::max(dp[i], dp[j]+arr[i]);
        }
    }

    std::cout << *std::max_element(dp, dp+N);

    return 0;
}