접근

수열 A의 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다
A={10,20,10,30,20,50} 일때 10,20,30,50 이 가장 긴 수열로 답은 5이다.

N의 범위는 1<=N<=1000 이기에 N 제곱의 알고리즘을 사용해도 무방하다.
처음 값부터 현재값 바로 전의 값까지 확인하면서 현재값보다 작으면 현재값은 그 값의 +1 해주면서 2중 포문을 돌리면 된다.

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

int N,ret;
int arr[1004];
int dp[1004];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N;
    
    for(int i=0;i<N;i++) {
        cin >> arr[i];
    }
    
    ret=dp[0];
    for(int i=1;i<N;i++) {
        for(int j=0;j<i;j++) {
            if(arr[i]>arr[j]) {
                dp[i]=max(dp[j]+1,dp[i]);
                ret=max(dp[i],ret);
            }
        }
    }
    cout << ret+1 << "\n";

    return 0;
}