[백준 알고리즘/C++/DP] 11722 가장 긴 감소하는 부분 수열

 

 

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 문제

 

 

DP오랜만이라 가장 긴 어쩌구 문제를 풀어봤다..

근데 헷갈리는거 실화인가.. ^^

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    int arr[1000], dp[1000];
    int res = 1;
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = 1;
 
        for (int j = 0; j < i; j++) {
            if (arr[i] < arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
 
            if (dp[i] > res) res = dp[i];
        }
    }
 
    cout << res;
}