11722번 가장 긴 감소하는 부분 수열

 간단한 DP 문제

 

 11053번과 거의 같은 문제

 

 

#include <iostream>
#include <algorithm>
#define MAX 1001
 
using namespace std;
 
int dp[MAX];
int A[MAX];
int N;
 
void DP(){
    int ans=0;
    
    for(int i=0;i<N;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(A[i]<A[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    
    cout << ans << endl;
}
 
int main(){
    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    
    DP();
}