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--;
}
}
}