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

백준 11054

알고리즘 분류 : dynamic programming (동적 계획법)

백준 11053번, LIS(Longest Increasing Subsequence)를 구하는 문제의 응용이다. 11053번과의 차이점은 LIS를 구하는 과정을, 두 번 거쳐야 한다는 점이다. 한 번은 왼쪽에서부터 증가할 때, 한 번은 오른쪽에서부터 증가할 때를 구해주면 된다.

LIS를 구하는 방법은 11053번과 동일하다.

왼쪽의 경우,
A[j]<A[i]를 만족할 때, len_left[i]=max(len_left[i],len_left[j]+1)
오른쪽의 경우,
A[j]<A[i]를 만족할 때, len_right[i]=max(len_right[i],len_right[j]+1)

두 배열을 완성시킨 후, 가장 큰 len_left[i]+len_right[i]-1의 값을 찾으면 된다. (A[i]에 해당하는 숫자를 공통으로 세었으니, 1을 빼준다.)

#include <iostream>
#include <algorithm>

using namespace std;
int A[1000];
int len_left[1000],len_right[1000];
int maxnum=0;

int main(){
	int N;
	cin >> N;
	
	for(int i=0; i<N; i++){
		cin >> A[i];
	}
	
	for(int i=0; i<N; i++){
		len_left[i]=1;
		for(int j=0; j<i; j++){
			if(A[j]<A[i]){
				len_left[i]=max(len_left[i],len_left[j]+1);
			}
		}
	} //왼쪽에서부터 증가하는 길이를 len_left에 저장
	for(int i=N-1; i>=0; i--){
		len_right[i]=1;
		for(int j=N-1; j>i; j--){
			if(A[j]<A[i]){
				len_right[i]=max(len_right[i],len_right[j]+1);
			}
		}
	} //오른쪽에서부터 증가하는 길이를 len_right에 저장
	
	for(int i=0; i<N; i++){
		maxnum=max(maxnum,len_left[i]+len_right[i]);
	}
	cout << maxnum-1 << '\n'; //len_left와 len_right간 공통된 부분 제거
}