14003 LIS5

์•Œ๊ณ ๋ฆฌ์ฆ˜ (LIS)

1. LIS ๋กœ ๊ตฌํ•จ
2. ์ˆ˜์—ด ์ถœ๋ ฅ
	1. LIS๊ตฌํ•˜๋ฉด์„œ, ํ˜„์žฌ LIS์˜ ์ธ๋ฑ์Šค๋ฅผ ํ•ญ์ƒ ์ €์žฅํ•จ
	2. LIS๋ฅผ ๊ตฌํ•˜๋ฉด, ๊ฐ€์žฅ ๋’ค์—์žˆ๋Š” LIS์˜ ๊ฐ€์žฅ ๋’ค ์›์†Œ์˜ ์ธ๋ฑ์Šค๊ฐ€ ์ €์žฅ๋จ
	3. ๊ทธ ์ธ๋ฑ์Šค๋กœ๋ถ€ํ„ฐ ๊ธธ์ด๋ฅผ ํ•˜๋‚˜์”ฉ์ค„์—ฌ๊ฐ€๋ฉฐ ์•ž์œผ๋กœ ๊ฐ€๋ฉด์„œ ๊ธธ์ด๊ฐ€ ๋งž๋Š”๊ฑธ ๋’ค์—์„œ๋ถ€ํ„ฐ ์ €์žฅ
	4. ๊ธธ์ด๊ฐ€ 0์ด๋˜๋ฉด ์ข…๋ฃŒ
	5. ์ด๋ ‡๊ฒŒํ•˜๋ฉด ๊ฐ€์žฅ ๋’ค์—์žˆ๋Š” LIS๊ฐ€ ์ €์žฅ๋œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#define MAX_LENGTH 1000001
 
using namespace std;
 
int lengthOfSequence, sequence[MAX_LENGTH], length[MAX_LENGTH], subSequence[MAX_LENGTH], longest, lis[MAX_LENGTH];
 
void LIS();
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> lengthOfSequence;
	for (int i = 1; i <= lengthOfSequence; i++)
		cin >> sequence[i];ใ…
	LIS();
	cout << longest << "\n";
	for (int i = 1; i <= longest; i++)
		cout << lis[i] << " ";
}
 
void LIS() {
	subSequence[0] = -2000000000;
	int lengthOfSub = 1;
 
	int longestIndex = 0;
	for (int i = 1; i <= lengthOfSequence; i++) {
		int* lb = lower_bound(subSequence, subSequence + lengthOfSub, sequence[i]);
		*lb = sequence[i];
		if (lb - subSequence == lengthOfSub)
			length[i] = lengthOfSub++;
		else
			length[i] = lb - subSequence;
 
		if (length[i] > longest) {
			longest = length[i];
			longestIndex = i;
		}
	}
 
	int temp = longest;
	for (int i = longestIndex; i >= 1; i--) {
		if (length[i] == temp) {
			lis[temp] = sequence[i];
			temp--;
		}
	}
}