[백준] 11053 가장 긴 증가하는 부분수열 c++

 

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

KEY

현재 자신과 이전에 나왔던 수들을 비교해가면서, 현재 자신 > 이전의 수를 만족할 경우에 길이+1을 해주고, 가장 긴 길이를 자신의 길이로 취한다. 

예시로 다음의 수열이 있다.

10 20 10 30 20 50

• 10부터 시작한다. 길이는 1이다.
• 20에 도착했다. 20>10을 만족하므로 길이는 1+1 = 2이다.
• 10에 도착했다. 자신보다 작은 수는 없으므로 길이는 1이다.
• 30에 도착했다. 30>10을 만족하므로 길이는 1+1 = 2이 될 수 있다. 30>20을 만족하므로 길이는 2+1 = 3이 될 수 있다. 이 중 길이가 가장 큰 것은 3이므로 길이는 3이 된다.
• 20에 도착했다. 20>10이므로 길이는 1+1 = 2이다.
• 50에 도착했다. 10부터 비교해봤을 때, 50>30의 경우 길이는 3+1이 가장 큰 경우이므로 길이는 4이다.

정답은 이 중 값이 가장 큰 4가 된다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
const int MAX = 1001;
int n;
int arr[MAX];
int dp[MAX] = { 1, };
int answer;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        int value = 0;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) { 
                value = max(value, dp[j]);
            }
        }
        dp[i] = value + 1; 
    }
 
    for (int i = 0; i < n; i++) {
        answer = max(answer, dp[i]);
    }
    cout << answer;
}