[코드트리 조별과제] [실버2] 가장 큰 증가 부분 수열

[코드트리][실버 2] 가장 큰 증가 부분 수열

https://www.codetree.ai/training-field/search/problems/largest-increasing-subsequence?&utm_source=clipboard&utm_medium=text

풀이

최장 증가 부분 수열 의 응용 문제

최장 증가 부분 수열과 거의 유사하나 길이가 아닌 합을 기준으로 세우면 된다.
최장 증가 부분 수열은 O(N²)과 이분탐색을 응용하는 O(N log N)의 2가지 방식이 존재하는데 우선 O(N²)로만 풀이하였다. 이분탐색은 구간합을 구하는 방법 때문에 보류하였다. 이후 방법을 찾게 되면 수정할 예정이다.

O(N²)의 경우에도 주의할 점이 있는데 길이가 가장 긴 수열이 합이 가장 큰 값인 것 아니기 때문에 증가 수열을 찾는 도중에 길이가 줄거나 같은 길이의 수열일지라도 지속적으로 가장 큰 합을 도출하는지 체크 해야 한다.

코드

O(N²)

#include<bits/stdc++.h>

constexpr int MAX = 1000;

int seq[MAX + 1];
int dp[MAX + 1];

int main(int argc, char** argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int n;
    std::cin >> n;
    seq[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> seq[i];
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            // 만일 현재 값보다 이전 값이 작다면
            if (seq[i] > seq[j])
            {
                if (dp[i] < dp[j] + seq[i])
                {
                    dp[i] = dp[j] + seq[i];
                }
            }
        }
    }

    int maxSum = -1;
    for (int i = 1; i <= n; i++)
    {
        if (maxSum < dp[i]) maxSum = dp[i];
    }

    std::cout << maxSum;

    return EXIT_SUCCESS;
}