가장 긴 증가하는 부분 수열 11053

문제

접근 방법

10	20	10	30	20	50
1	2	1	3	2	4

현재 인덱스를 기준으로 앞을 확인해보며 자신보다 작은 값이 있으면 현재의 길이를 유지하거나 자신보다 작은 값의 길이의 +1한 것으로 교체하는 방식으로 접근하면 된다.
즉 DP[I]=MAX(DP[I],DP[J]+1)인 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, ret = 0;
    cin >> N;
    vector<int> A(N), dp(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> A[i];
        dp[i] = 1;
        for (int j = 0; j < i; ++j)
        {
            if (A[i] > A[j])
            {
                dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
            }
        }
        ret = ret > dp[i] ? ret : dp[i];
    }
    cout << ret;
}

풀이

수열의 크기가 1000이기에 2중 반복문을 사용해도 괜찮다.
그렇기에 가장 긴 길이를 골라오면 된다.