[백준 C++] 11054번: 가장 긴 바이토닉 부분 수열

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

 

증가하는 부분 수열, 감소하는 부분수열이 아닌 가장 긴 바이토닉 부분 수열이다.

 

이전 증가하는 부분 수열이나 감소하는 부분수열의 경우 dp를 통해서 dp[i]까지 가장 긴 부분수열의 길이를 저장해주고 비교하여 풀었었는데 이번에도 똑같이 설정은 해주자.

 

수열을 담을 a[1001]을 선언해준뒤 이번에는 dp를 이차원으로 선언해준다.

 

그 이유는 dp[i][0]에는 증가하는 부분수열, dp[i][1]에는 감소하는 부분수열을 담고 그 합에서 -1을 하여 답을 구하려 하기 때문이다. -1을 해주는 이유는 겹치는 수 하나를 빼고 계산해야하기 때문이다.

 

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
int dp[MAX][2] = { 0, };
int a[MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n, ans = 0;
	cin >> n;
 
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
 
 
	for (int i = 0; i < n;i++) {
		dp[i][0] = 1;
		for (int j = i - 1;j >= 0;j--) {
			if (a[i] > a[j]) {
				dp[i][0] = max(dp[i][0],(dp[j][0] + 1));
			}
		}
	}
 
	for (int i = n-1; i >= 0;i--) {
		dp[i][1] = 1;
		for (int j = i + 1;j < n;j++) {
			if (a[i] > a[j]) {
				dp[i][1] = max(dp[i][1], (dp[j][1] + 1));
			}
		}
	}
 
	for (int i = 0;i < n;i++) {
		ans = max(ans, dp[i][0] + dp[i][1] - 1);
	}
 
	cout << ans << '\n';
 
	return 0;
}