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

문제 링크

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

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

 

가장 긴 바이토닉 부분 수열을 구하기 위해서는

1. 가장 긴 증가하는 부분 수열을 왼쪽에서 오른쪽으로 구한다.

2. 가장 긴 증가하는 부분 수열을 오른쪽에서 왼쪽으로 구한다.

3. 1번과 2번의 각 자리를 더한 값 중 최대값을 구한다.

4. 최대값에서 -1을 뺀다.

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main(){
	int n;
	int d[1001];
	int cnt1[1001];
	int cnt2[1001];
	int cnt3[1001];
	int ans=0;
	cin >> n;
	for(int i=0;i<n;i++)
	cin >> d[i];
	for(int i=0;i<n;i++){
	cnt1[i]=1;
	for(int j=0;j<i;j++){
	if(d[i]>d[j]){
	cnt1[i] = max(cnt1[i],cnt1[j]+1);
	}
	}
	}
	for(int i=n-1;i>=0;i--){
	cnt2[i]=1;
	for(int j=n-1;j>i;j--){
	if(d[i]>d[j]){
	cnt2[i] = max(cnt2[i],cnt2[j]+1);
	}
	}
	}
	for(int i=0;i<n;i++){
	cnt3[i] = cnt1[i] + cnt2[i];
	ans = max(sum,cnt3[i]);
	}
	cout << ans - 1 << endl;
	return 0;
	}

view raw 11054.cpp hosted with ❤ by GitHub