BOJ 11054. 가장 긴 바이토닉 부분 수열
랭크 : 골드3
문제 풀이
LIS 알고리즘을 왼쪽에서 한번 오른쪽에서 한번 사용해서 이를 합친 것이 젤 큰 경우를 찾습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N;
int main() {
fastio;
cin >> N;
vector<int> arr(N, 0);
for (int i=0; i < N; i++) {
cin >> arr[i];
}
vector<int> ans(N, 0);
vector<int> up;
for (int i=0; i < N; i++) {
auto a = lower_bound(up.begin(), up.end(), arr[i]);
ans[i] = a - up.begin();
if (a == up.end()) up.push_back(arr[i]);
else *a = arr[i];
}
vector<int> down;
for (int i=N - 1; i >= 0; i--) {
auto a = lower_bound(down.begin(), down.end(), arr[i]);
ans[i] += a - down.begin();
if (a == down.end()) down.push_back(arr[i]);
else *a = arr[i];
}
// for (int i=0; i < N; i++) {
// cout << ans[i] << " ";
// }
// cout << endl;
cout << *max_element(ans.begin(), ans.end()) + 1 << endl;
}
알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| LIS | $O(N)$ | $O(N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 17298. 오큰수 (0) | 2022.07.17 |
|---|---|
| BOJ 1450. 냅색문제 (0) | 2022.07.17 |
| BOJ 2293. 동전 1 (0) | 2022.07.16 |
| BOJ 3015. 오아시스 재결합 (0) | 2022.07.16 |
| BOJ 2629. 양팔저울 (0) | 2022.07.15 |