[C++] 14002 : 가장 긴 증가하는 부분 수열 4

골드 Ⅳ

 

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

using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	vector <int> seq;
	int s;
	for (int i = 0; i < n; i++) {
		scanf("%d", &s);
		seq.push_back(s);
	}

	vector <int> subsq;
	subsq.push_back(seq[0]);

	vector <int> pos;
	pos.resize(n);
	pos[0] = 1;

	int idx;
	for (int i = 1; i < n; i++) {
		if (subsq.back() < seq[i]) {
			subsq.push_back(seq[i]);
			pos[i] = subsq.size();
		}
		else {
			idx = lower_bound(subsq.begin(), subsq.end(), seq[i]) - subsq.begin();
			subsq[idx] = seq[i];
			pos[i] = idx + 1;
		}
	}

	vector <int> LIS;
	int len = subsq.size();

	for (int i = n - 1; i >= 0; i--) {
		if (pos[i] == len) {
			LIS.push_back(seq[i]);
			len--;
		}
	}

	printf("%d\n", LIS.size());
	while (!LIS.empty()) {
		printf("%d ", LIS.back());
		LIS.pop_back();
	}

}

 

LIS 알고리즘 (nlogn, LIS 출력)

 

가장 긴 증가하는 부분 수열 5의 제출 코드와 똑같으므로 거기서 설명..

4가 골드 4인 이유는 n이 크지 않아서 (<1000 인가)

 

아마 dp로도 풀리나보다 그래서 골드 4인 듯