[ 백준 11055 ] 가장 큰 증가 부분 수열 (C++)

백준의 가장 큰 증가 부분 수열(11055) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

문제를 풀기 전에, 굉장히 유사한 아래의 먼저 풀어보신 후, 풀이까지 보고 오는 것을 권장드립니다.

[ 백준 - 가장 긴 증가 부분 수열(11053) 문제 바로가기 ]

[ 백준 - 가장 긴 증가 부분 수열(11053) 풀이 바로가기 ]

이 문제는 위의 문제와 굉장히 비슷한 문제이다.

위의 문제에서는, 단순히 가장 긴 증가하는 부분 수열의 길이를 구하는 문제였지만, 이 문제에서는 길이가 아닌 그 합을 구하면 되는 문제이다.

따라서, 위와 똑같은 알고리즘으로 문제에 접근하되, DP[] 라는 배열에 저장되는 값을 부분 수열의 길이가 아닌, 증가하는 부분 수열의 합을 저장해 주면 된다.

( 위의 풀이글과 굉장히 유사한 풀이이기 때문에, 구체적인 풀이에 대해서는 설명을 하지 않겠습니다 ! )

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    int Answer = 0;
    for (int i = 1; i <= N; i++)
    {
        DP[i] = Arr[i];
        for (int j = 1; j < i; j++)
        {
            if (Arr[i] > Arr[j]) DP[i] = Max(DP[i], DP[j] + Arr[i]);
        }
        Answer = Max(Answer, DP[i]);
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}