(백준/c++) 11054번 - 가장 긴 바이토닉 부분수열

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

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

* 문제 풀이 알고리즘

문제 내에 있는 예제를 예시로 들면,

{1  5  2  1  4  3  4  5  2  1} 에서 가장 긴 바이토닉 부분 수열은 

{1, 2, 3, 4, 5, 2, 1} = 답 7이 됩니다. 

밑에 작성한 알고리즘은 왼쪽에서 부터 증가하는 부분 수열의 DP(InC)와 

오른쪽에서 부터 증가하는 부분 수열의 DP(DeC)를 구해서 그 합 중 가장 

큰 수가 해답이 되도록 작성하였습니다. 

InC = { 1, 2, 2, 1, 3, 3, 4, 5, 2, 1 }

DeC = { 1, 5, 2, 1, 4, 3, 3, 3, 2, 1 }

	InC = { 1, 2, 2, 1, 3, 3, 4, 5, 2, 1 }
	DeC = { 1, 5, 2, 1, 4, 3, 3, 3, 2, 1 }
	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int main(void)
	{
	std::ios::sync_with_stdio(false);
	std::cin.tie();
	std::cout.tie();
	// ===========================
	int N; cin >> N;
	vector<int> seq(N);
	for (int i = 0; i < N; i++)
	cin >> seq[i];
	// ===========================
	vector<int> InC(N,1), DeC(N,1);
	for(int i =1; i < N; i++)
	for (int j = 0; j < i; j++)
	{
	if (seq[i] > seq[j])
	InC[i] = max(InC[j] + 1, InC[i]);
	if(seq[N-i-1]>seq[N-j-1])
	DeC[N - i - 1] = max(DeC[N - j - 1 ] + 1, DeC[N - i - 1]);
	}
	// ===========================
	int _max = -1000;
	for (int i = 0; i < N; i++)
	{
	if (_max < InC[i] + DeC[i])
	_max = InC[i] + DeC[i];
	}
	cout << _max - 1;
	}

view raw gistfile1.txt hosted with ❤ by GitHub