11055 가장 큰 증가 부분 수열

11055. 가장 큰 증가 부분 수열 / c++ / Silver2 / 10분

문제

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

1. 길이가 N인 수열 A가 주어진다.
2. 증가 부분 수열 중 가장 합이 큰 값을 출력

접근 방식

동적 프로그래밍

1. dp[i]는 i보다 왼편의 값 중 증가 부분 수열에 해당하며 그 합이 가장 큰 dp[j] + arr[i]
2. 만약 dp[i]가 answer 보다 크다면 answer 최신화

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;
inline int MAX(int A, int B) { return A > B ? A : B; }
int N;
int arr[1'001];
int dp[1'001];

int answer = 0;

int DP(int num)
{
    if (dp[num] == 0)
    {
        int maxNum = 0;
        for (int i = 1; i < num; ++i)
        {
            if (arr[i] < arr[num])
                maxNum = MAX(maxNum, dp[i]);
        }
        
        dp[num] = maxNum + arr[num];
    }
    
    answer = MAX(answer, dp[num]);
    
    return dp[num];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> N;
    
    for (int i = 1; i <= N; ++i)
    {
        cin >> arr[i];
        
        DP(i);
    }
    
    cout << answer << '\n';
    
    return 0;
}

다시 생각해 볼 점

1. dp[i] = dp[left] + arr[i] 형식