[BOJ 11054] 가장 긴 바이토닉 부분 수열(c++)

https://www.acmicpc.net/problem/11054

 

문제 개요

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 가장 긴 바이토닉 수열의 크기를 구해야 한다.

(1 <= N <= 1,000)

(1 <= A <= 1,000)

 

문제 풀이

https://doyun98.tistory.com/112

[알고리즘] LIS(최장 증가 부분 수열)

양방향의 LIS를 모두 구하여 해결하였다. LIS를 구현하며 각 요소마다의 부분 수열의 크기를 저장하고, n - 1부터 0까지의 반대 방향으로도 LIS를 구하며 크기를 갱신하였고, 그 중 가장 큰 값을 찾아 가장 큰 바이토닉 수열의 크기를 찾았다. 문제에서는 N이 1도 가능하기 때문에 따로 처리가 필요하였는데, 이 때문에 트러블 슈팅이 오래 걸렸다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, res = 1;
vector<int> arr;
int dp[10010], lis[1001], r_lis[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	arr.reserve(n);
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		arr.push_back(x);
	}
	lis[0] = arr[0];
	int size = 1;
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		if (lis[size - 1] < arr[i]) {
			lis[size] = arr[i];
			dp[i] = ++size;
		}
		else {
			int pos = lower_bound(lis, lis + size, arr[i]) - lis;
			lis[pos] = arr[i];
			dp[i] = pos + 1;
		}
		res = max(res, dp[i]);
	}
	size = 1;
	r_lis[0] = arr[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		if (r_lis[size - 1] < arr[i]) {
			r_lis[size] = arr[i];
			dp[i] += size++;
		}
		else {
			int pos = lower_bound(r_lis, r_lis + size, arr[i]) - r_lis;
			r_lis[pos] = arr[i];
			dp[i] += pos;
		}
		res = max(res, dp[i]);
	}
	cout << res;
	return 0;
}