[백준 11055] 알고리즘 47일차 : 가장 큰 증가 부분 수열

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

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

동적계획법 C++

이번엔 가장 큰 증가하는 부분 수열의 합 구하기

 

접근 방법

지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다.

차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우

길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로

비교할 때 이 부분을 주의해야 했다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n ;

    int num[n];
    int max[n];
    int result = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
        max[i] = num[i];
        for(int j = 0 ; j < i ; j++){
            if(num[j] < num[i] && max[j]+num[i] >= max[i]){
                max[i] = max[j]+num[i];
            }
        }
        if(result < max[i])
            result = max[i];
    }
    
    cout << result;
    return 0;
}