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

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

풀이

dp(i)를 i번째 원소가 포함된, 증가하는 부분 수열의 최대 길이라고 하자.

i번째 원소가 i>j인 j번째 원소보다 크면
dp(i) = dp(j) + 1 이다.

j가 2개 이상일 경우, i보다 작은 여러 j에 대해서
dp(i) = dp(j)의 최댓값 + 1 이다.

그리고 최종 결과는 dp(i)의 최댓값이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, ans;
    cin >> n;
    
    vector<int> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    
    vector<int> dp(n, 1);
    if(n == 1) cout << 1;
    else {
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(v[i] > v[j]) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        cout << *max_element(dp.begin(), dp.end());
    }
    return 0;
}