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

#include <iostream>
#include <vector>
#include <algorithm>
 
int arr[1001] = {};
 
int DPRight[1001] = {};
int DPLeft[1001] = {};
 
int main()
{
	int N = 0;
	std::cin >> N;
 
	for (int i = 0; i < N; ++i)
	{
		std::cin >> arr[i];
	}
 
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (arr[i] > arr[j])
			{
				DPRight[i] = std::max(DPRight[j] + 1, DPRight[i]);
			}
		}
	}
 
	for (int i = N - 1; i >= 0; --i)
	{
		for (int j = N - 1; j >= i; --j)
		{
			if (arr[i] > arr[j])
			{
				DPLeft[i] = std::max(DPLeft[j] + 1, DPLeft[i]);
			}
		}
	}
 
	int iMax = 0;
	int iMaxNumber = 0;
	for (int i = 0; i < N; ++i)
	{
		if (iMax < DPRight[i] + DPLeft[i])
		{
			iMax = DPRight[i] + DPLeft[i];
			iMaxNumber = i;
		}
	}
 
	std::cout << DPRight[iMaxNumber] + DPLeft[iMaxNumber] + 1;
 
	return 0;
}

 

왼쪽부터 순서에 따라서 가장 큰 것, 오른쪽부터 순서에 따라서 가장 큰 것들을 구해서

그 두개를 더했을 때 가장 큰 것을 입력했습니다.