[백준 BoJ] 14002 - 가장 긴 증가하는 부분 수열 4

// https://www.acmicpc.net/problem/14002
// 가장 긴 증가하는 부분 수열 4
#include<iostream>
#include<algorithm>
#include<vector>
int dp[1000002];
int arr[1000002];
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	vector<int> v;
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	dp[1] = 1;
	
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j]);
		}
		dp[i]++;
	}

	int Max = 0, MaxIdx;

	for (int i = 1; i <= N; i++) {
		if (dp[i] > Max) {
			MaxIdx = i;
			Max = dp[i];
		}
	}

	cout << dp[MaxIdx] << "\n";
	int Maxcnt = dp[MaxIdx];
	for (int i = MaxIdx; i >= 1; i--) {
		if (dp[i] == Maxcnt) {
			v.push_back(arr[i]);
			Maxcnt--;
		}
	}
	sort(v.begin(), v.end());
	for (auto V : v) {
		cout << V << " ";
	}
}