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

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

---

해설

이번 문제는 LIS의 끝판왕 가장 긴 증가하는 수열 5 문제이다.

역시 쉽지 않았다.

https://far-simple.tistory.com/43

전에 썼던 이 방법을 사용했다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, arr[1000001], p[1000001], cnt;
vector<int> ans, print;
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	ans.push_back(arr[1]);
	for (int i = 2; i <= n; i++) {
		if (ans[cnt] < arr[i]) {
			ans.push_back(arr[i]);
			cnt++;
			p[i] = cnt;
		}
		else {
			int pos = lower_bound(ans.begin(), ans.end(), arr[i]) - ans.begin();
			ans[pos] = arr[i];
			p[i] = pos;
		}
	}
	cout << cnt + 1 << '\n';
	for(int i=n; i>=1 && cnt >=0; i--){
		if (p[i] == cnt) {
			print.push_back(arr[i]);
			cnt--;
		}
	}
	for (int i = print.size() - 1; i >= 0; i--)
		cout << print[i] << ' ';
}