백준 14402번 가장 긴 증가하는 부분 수열 4 C++

출처 : https://www.acmicpc.net/problem/14002

 

lis 문제랑 똑같이 었는데, parent 배열을 하나 만들어서 수열의 인덱스를 저장해서 어떤 수열인지 추적하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> dp(n, 1);
    vector<int> parent(n);
    int ans = 1;
    int end = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[i] <= v[j]) continue;
            if (dp[j] + 1 <= dp[i]) continue;
            dp[i] = dp[j] + 1;
            parent[i] = j;
            if (dp[i] > ans) {
                ans = dp[i];
                end = i;
            }
        }
    }
    vector<int> ansVec;
    while (true) {
        ansVec.push_back(v[end]);
        if (end == parent[end]) break;
        end = parent[end];
    }
    reverse(ansVec.begin(), ansVec.end());
    cout << ans << "\n";
    for (auto a : ansVec) {
        cout << a << " ";
    }
}