[C++] 백준 14003번 : 가장 긴 증가하는 부분 수열5

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

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

---

문제 접근

 LIS 4번 문제와 다른 점은 인풋의 갯수와 크기 뿐이다. 따라서 이전과 동일하다.

코드

#include <iostream>

using namespace std;

int n;
int arr[1000001], dp[1000001], p[1000001];

int binary(int left, int right, int key) {
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (dp[mid] >= key) right = mid - 1;
		else left = mid + 1;
	}
	return left;
}

void backtrace(int idx, int len) {
	if (idx < 0) return;
	if (p[idx] == len) {
		backtrace(idx - 1, len - 1);
		cout << arr[idx] << " ";
	}
	else backtrace(idx - 1, len);
}

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];
	int idx = 0;
	for (int i = 0; i < n;i++) {
		if (dp[idx] < arr[i]) dp[++idx] = arr[i];
		else {
			int lower_bound = binary(0, idx, arr[i]);
			dp[lower_bound] = arr[i];
		}
		p[i] = binary(0, idx, arr[i]) + 1;
	}
	cout << idx + 1 << "\n";
	backtrace(n, idx + 1);
}