[BOJ/C++]11722번 가장 긴 감소하는 부분 수열

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

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

---

문제

수열 A가 주어졌을 때 가장 긴 감소하는 부분 수열을 구해라

 

풀이

https://lionontheshore.tistory.com/38?category=929275

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

여기서 조건만 조금 만졌음.

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int arr[n+1];
    int dp[n+1];
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    
    int max_num=0;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(arr[i]<arr[j])
                dp[i]=max(dp[i],dp[j]+1);
        }
        max_num=max(max_num,dp[i]);
    }
    cout<<max_num<<endl;
}