[알고리즘 문제] 백준11055 - 가장 큰 증가 부분 수열

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

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

LIS의 변형 문제로, LIS의 증가하는 수열의 최대 길이를 구하는 문제 였다면 이 문제는 "증가하는 부분 수열중에 최대합"을 구하는 문제 입니다.

 

[1, 100, 2, 50, 60, 3, 5, 6, 7, 8] 의 경우 LIS는 [1,2,3,5,6,7,8]이지만 합이 가장 큰 경우는 [1,2,50,60]으로 113이 됩니다. 

 

문제 해결을 위해 dp[], arr[] 배열을 사용하였고 arr[]은 숫자를 입력받고 dp[]는 arr[i]번째 위치하는 숫자의 최대값을 저장하는데 사용합니다. 여기서 중요한 점은 dp[i]에는 어떤 정수의 증가 부분 수열을 만족하는 최대값을 가지고 있기 때문에 dp[i+1]에는 1 ~ i까지 dp[]에서 최대값을 구한 다음 dp[i+1]에 최대값 + arr[i]를 넣어주면 됩니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

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

    int arr[1001] = {0};
    int dp[1001] = {0};

    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        int sum = 0;
        for (int j = 1; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                sum = max(sum, dp[j]);
            }
        }
        dp[i] = sum + arr[i];
        mx = max(mx, dp[i]);
    }

    cout << mx;
    return 0;
}