[백준][C++][LIS,DP]11054번. 가장 긴 바이토닉 부분 수열

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

 

 

바이토닉 수열 중에 가장 긴 길이를 찾으려면 LIS 알고리즘을 사용하면된다.

이 LIS를 왼쪽에서 오른쪽으로 가면서 i번째를 기준으로 하는 가장 긴 증가하는 부분 수열 길이를 구하고 

오른쪽에서 왼쪽으로 가면서  i번째를 기준으로 하는 가장 긴 감소하는 부분 수열 길이를 더하고 중복되는 i번째를 빼주면 된다.

 

 

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp_lis(vector<int>& v)
{
	int size = v.size();
	vector<int> dp1(size, 1), dp2(size, 1);

	//왼쪽->오른쪽
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[j] < v[i])
			{
				dp1[i] = max(dp1[i], dp1[j] + 1);
			}
		}
	}

	//오른쪽->왼쪽
	for (int i = size - 1; i >= 0; i--)
	{
		for (int j = size - 1; j > i; j--)
		{
			if (v[j] < v[i])
			{
				dp2[i] = max(dp2[i], dp2[j] + 1);
			}
		}
	}

	// 각 `i`에서 `dp1[i] + dp2[i] - 1`의 최댓값 찾기
	int maxLength = 0;
	for (int i = 0; i < size; i++) {
		maxLength = max(maxLength, dp1[i] + dp2[i] - 1);
	}

	return maxLength;
}


int main()
{
	int n;
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	cout << dp_lis(v) << "\n";
}