1번과는 다르게 배열의 크기만 다르다.
마찬가지로 lower_bound를 사용했다.
BOJ: https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int lis, n;
int arr[1000000];
int Lis[1000001];
int lower_bound(int start, int end, int key) {
int mid;
while (start < end) {
mid = (start + end) / 2;
if (Lis[mid] < key)
start = mid + 1;
else
end = mid;
}
return end + 1;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
lis = 0, Lis[0] = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > Lis[lis]) {
Lis[lis + 1] = arr[i], lis++;
}
else {
int ans = lower_bound(0,lis,arr[i]);
Lis[ans-1] = arr[i];
}
}
cout << lis+1;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
복습 20.02.09
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 1965번 상자넣기 (0) | 2019.04.07 |
|---|---|
| BOJ 1937번 욕심쟁이 판다 (0) | 2019.04.06 |
| BOJ 14003번 가장 긴 증가하는 부분수열5 (0) | 2019.04.06 |
| BOJ 14002번 가장 긴 증가하는 부분수열4 (0) | 2019.04.06 |
| 가장 긴 증가하는 부분수열3(12738) - Junnnho (0) | 2019.04.06 |