[백준 DP] 11054번 - 가장 긴 바이토닉 부분 수열

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

 

<코드>

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

int N;
int arr[1001] = { 0, };
int dp_In[1001] = { 0, };
int dp_De[1001] = { 0, };
int max_Value = 0;

int main() {
	cin >> N; 

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= N; i++) { //증가하는 부분수열의 길이 구하기 
		dp_In[i] = 1;

		for (int j = 1; j < i; j++) {
			if (arr[j] < arr[i] && dp_In[i] < dp_In[j] + 1) dp_In[i] = dp_In[j] + 1;
		}
	}

	for (int i = N; i >= 1; i--) { //감소하는 부분수열의 길이 구하기 
		dp_De[i] = 1;

		for (int j = N; j > i; j--) {
			if (arr[j] < arr[i] && dp_De[i] < dp_De[j] + 1) dp_De[i] = dp_De[j] + 1;
		}
	}

	for (int i = 1; i <= N; i++) { //증감 부분수열의 합 
		arr[i] = dp_In[i] + dp_De[i];
		if (max_Value < arr[i]) max_Value = arr[i]; //합의 최댓값
	}
	
	cout << max_Value - 1 << endl;

	return 0;
}