[Algorithm]Baekjoon 11055 : 가장 큰 증가하는 부분수열

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

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

 
int n;
int arr[1001] = { 0 };
int dp[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    int answer = arr[0];
    dp[0] = arr[0];
 
    for (int i = 1; i < n; ++i)
    {
        dp[i] = arr[i];
 
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] < arr[i])
            {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
 
        answer = max(answer, dp[i]);
    }
 
    cout << answer;
}
 

가장 길게 증가하는 부분수열이 아닌, 가장 크게 증가하는 부분수열을 구하는 문제이다.

길게 증가하는걸 잘 이해했으면 어렵지않게 풀 수 있다.