14003 LIS5
알고리즘 (LIS)
1
2
3
4
5
6
7
1. LIS 로 구함
2. 수열 출력
1. LIS구하면서, 현재 LIS의 인덱스를 항상 저장함
2. LIS를 구하면, 가장 뒤에있는 LIS의 가장 뒤 원소의 인덱스가 저장됨
3. 그 인덱스로부터 길이를 하나씩줄여가며 앞으로 가면서 길이가 맞는걸 뒤에서부터 저장
4. 길이가 0이되면 종료
5. 이렇게하면 가장 뒤에있는 LIS가 저장된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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--;
}
}
}