문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

풀이

이 문제를 풀기 위해서 가장 긴 증가하는 부분 수열 문제와 가장 긴 감소하는 부분 수열 문제 방식을 이용했다. DP배열을 이중배열로 할당하고 0번째 행은 증가하는, 1번째 행은 감소하는 부분 수열의 길이를 넣어두고 두 길이를 합한 값이 가장 큰 것을 결과물로 제출했다.

코드

#include <iostream>
using namespace std;

void	ft_free(int **DP, int *res, int *arr, int n) {
	for (int i = 0; i < 2; i++)
		delete[] DP[i];
	delete[] DP;
	delete[] res;
	delete[] arr;
}
int main()
{
	int n;
	int result = 0;
	scanf("%d", &n);
	int* arr = new int[n];
	int* res = new int[n];
	int** DP = new int*[2];
	for (int i = 0; i < 2; i++)
	{
		DP[i] = new int[n];
		for (int j = 0; j < n; j++)
		{
			if (i == 0)
				scanf("%d", &arr[j]);
			DP[i][j] = 1;
		}
	}		
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[j] < arr[i] && DP[0][j] >= DP[0][i])
				DP[0][i] = DP[0][j] + 1;
		}
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = n-1 ; j > i ; j--)
			if (arr[j] < arr[i] && DP[1][j] >= DP[1][i])
				DP[1][i] = DP[1][j] + 1;
	}
	for (int i = 0; i < n; i++)
	{
		res[i] = DP[0][i] + DP[1][i];
		if (result < res[i])
			result = res[i];
	}
	cout << result - 1;
	ft_free(DP, res, arr, n);
	return (0);
}