백준 7861번 Longest Ordered Subsequence [C++]

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

 

 

#문제 간단 정리

가장 긴 부분수열 찾는문제 

dp 이고 웰노운이다

 

#문제 해결 방법

웰노운 문제라서 따로 해설을 첨부하지는 않겟다.

 

#전체 코드

#include <iostream>
#include <vector>

using namespace std;





int main() {
    
    int n;
    cin >> n;

    vector<int> vec(n);

    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }


    vector<int> dp(n,1);
    int maxlen = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i ; j++) {
            if (vec[i] > vec[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                maxlen = max(dp[i], maxlen);
            }
        }
    }

    cout << maxlen << '\n';

    return 0;
}