백준 11055 - 가장 큰 증가 부분 수열

문제

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

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

 

풀이

가장 긴 증가하는 부분 수열 문제와 유사한 문제다. 

d[n] = arr[n]을 포함하는 증가하는 부분 수열의 합 이라고 하면

i = 1 부터 i = n-1 까지 증가 하는 부분 수열의 조건에 맞는 d[i]의 최대 값을 구해 arr[n] 값을 더해주면 최대 d[n]이 나온다.

 

d[n] = max{

  d[i] (i = 1 부터 i = n-1 까지 이고 arr[i] < arr[n])

} + arr[n] 이 되고

 

1 부터 n까지 d[n]의 최댓값을 찾으면 된다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int dp[1001];
int arr[1001];
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i];
 
    for (int i = 1; i <= N; i++)
    {
        dp[i] = arr[i];
        for (int j = 1; j < i; j++)
        {
            if (arr[j] < arr[i] && dp[i] < dp[j] + arr[i]) dp[i] = dp[j] + arr[i];
        }
    }
 
    for (int i = 1; i <= N; i++) result = max(result, dp[i]);
 
    cout << result;
 
    return 0;
}