[백준][DP] 가장 긴 감소하는 부분 수열

1. 문제 주소

acmicpc.net/problem/11722

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

2. 문제

i = n-1인 수가 가장 처음으로 오는 수열의 최대 길이를 구하는 방식으로 코드를 작성하였다.

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
 
    vector<int> len(n);
 
    for (int i = n - 1; i >= 0; i--) {
        len[i] = 1;
        for (int j = n - 1; j > i; j--) {
            if (A[i] > A[j] && len[i] < len[j] + 1) {
                len[i] = len[j] + 1;
            }
        }
    }
 
    int result = *max_element(len.begin(), len.end());
    cout << result << '\n';
    return 0;
}