[C/C++] BOJ 11055 :: 가장 큰 증가 부분 수열

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

문제 링크 : https://www.acmicpc.net/problem/11055

나의 풀이

1. 가장 큰 증가 부분 수열을 저장할 1차원 배열을 생성한다.

2. 기준 idx를 두고 그 앞 범위를 탐색하며 증가 부분 수열일 될 때, 그 합을 갱신한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11055/BOJ_11055.cpp

// 백준알고리즘 11055번 :: 가장 큰 증가 부분 수열
#include<iostream>
using namespace std;
#define max(a,b) (a > b) ? a : b
 
int N;
int arr[1001];
int dp[1001];
 
int main(void)
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    for (int i = 0; i < N; i++)
    {
        dp[i] = arr[i];
        for (int j = 0; j < i; j++)
        {
            // 증가하는 수열일 때, 합을 갱신한다.
            if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + arr[i]);
        }
    }
 
    int ans = dp[0];
    for (int i = 1; i < N; i++)
        if (ans < dp[i]) ans = dp[i];
 
    cout << ans;
 
    return 0;
}