[BAE/<JOON> 문제풀이] 14003. 가장 긴 증가하는 부분 수열 5(풀이 미완)

www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

struct trackball {
	int idx, val;
};
int main()
{
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	vector<int> dp;
	vector<trackball> track(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	dp.push_back(arr[1]);
	track[1] = { 0, arr[1] };
	for (int i = 2; i <= n; i++) {
		if (arr[i] > *(dp.end() - 1)) {
			dp.push_back(arr[i]);
			track[i] = { (int)dp.size() - 1, arr[i] };
		}
		else {
			auto lb = lower_bound(dp.begin(), dp.end(), arr[i]);
			*lb = arr[i];
			track[i] = { lb - dp.begin(), arr[i] };
		}
	}

	cout << dp.size() << "\n";

	vector<int> path;
	int tc = dp.size() - 1;
	for (int i = n; i >= 1; i--) {
		if (track[i].idx == tc) {
			path.push_back(track[i].val);
			tc--;
		}
		if (tc == -1) break;
	}

	for (int i = path.size() - 1; i >= 0; i--) {
		cout << path[i] << " ";
	}
	
	return 0;
}