문제
풀이
12015번에서 최대 부분 수열을 출력하는게 추가된 문제이다. 12015번에서는 최대 길이만을 보장할 뿐, result 배열의 값이 최대 부분 수열이라는 것을 의미하는 것은 아니다. 그래서 추적을 하기 위해서 index를 labeling하여 최대 부분 수열을 출력하게끔 한다. 코드는 Reference에서 참조하였다.
소스 코드
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <algorithm>
#include <vector>
#define endl "\n"
#define MAX 1000010
using namespace std;
int N;
int Arr[MAX];
int Index_Arr[MAX];
vector<int> V;
void Input()
{
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> Arr[i];
}
}
void Solution()
{
for (int i = 1; i <= N; i++)
{
if (V.size() == 0 || V[V.size() - 1] < Arr[i])
{
V.push_back(Arr[i]);
Index_Arr[i] = V.size() - 1;
}
else
{
int Left = 0;
int Right = V.size() - 1;
while (Left < Right)
{
int Mid = (Left + Right) / 2;
if (V[Mid] >= Arr[i]) Right = Mid;
else Left = Mid + 1;
}
V[Left] = Arr[i];
Index_Arr[i] = Left;
}
}
cout << V.size() << endl;
vector<int> Answer;
int Find_Index = V.size() - 1;
for (int i = N; i > 0; i--)
{
if (Index_Arr[i] == Find_Index)
{
Find_Index--;
Answer.push_back(Arr[i]);
}
}
for (int i = Answer.size() - 1; i >= 0; i--) cout << Answer[i] << " ";
cout << endl;
}
void Solve()
{
Input();
Solution();
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
//출처: https://yabmoons.tistory.com/561 [얍문's Coding World..]
