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

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

11054번: 가장 긴 바이토닉 부분 수열

 

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

int n;
vector<int> arr(1001, 0);
vector<int> dp(1001, 1);
vector<int> r_dp(1001, 1);

int main() {
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	for(int y = 0; y < n; y++){
		for(int x = 0; x < y; x++){
			if(arr[x] < arr[y])
				dp[y] = max(dp[y], dp[x] + 1);
		}
	}
	for(int y = n - 1; y >= 0; y--){
		for(int x = n - 1; x >= y; x--){
			if(arr[x] < arr[y])
				r_dp[y] = max(r_dp[y], r_dp[x] + 1);
		}
	}
	
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = max(dp[i] + r_dp[i] - 1, ans);
	}
	cout << ans << endl;
	return 0;
}

 

dp에는 자기 이전에 있는 원소들에 대한 증가하는 부분수열을, r_dp에는 자기 이후에 있는 원소들에 대한 감소하는 부분수열을 저장한다. 모든 원소들의 (dp값 + r_dp값 - 1) 중 최댓값이 정답이 된다. 해당 원소가 중복되기 때문에 -1을 해주어야 한다.