출처 BOJ

가장 긴 바이토닉 부분 수열

문제

수열 S가 어떤 수 $S_{k}$를 기준으로 $S_{1} \lt S_{2} \lt ... S_{k-1} \lt S_{k} \gt S_{k+1} ... \gt S_{N-1} \gt S_{N}$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {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를 이루고 있는 $A_{i}$가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ $A_{i}$ ≤ 1,000)

출력

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

예제

범위체크

최대 길이 1000 $\lt INT$

풀이

양방향에서 커지는 수열의 개수를 구한후 그들의 (합-1)이 가장 긴 것 → 답

• 증가하는 가장 긴 수열 구하는 법
  A[n] = n이전 값들의 Cnt[i] 중 가장 큰값 + 1

  코드

  code

#include<cstdio>
#include<iostream>
#define BOUND 1002

using namespace std;

int N;
int A[BOUND],Cnt[BOUND],Cnt2[BOUND];
int MAX = 0;

void find(){
	for(int n=1; n<N; n++){
		for(int i=0; i<n; i++){
			if(A[i] < A[n])
				Cnt[n] = max(Cnt[n],Cnt[i]+1);
			if(A[N-i] < A[N-n])
				Cnt2[N-n] = max(Cnt2[N-n],Cnt2[N-i]+1);
		}
	}

	
	for(int i=1; i<N; i++){
		int sum =  Cnt[i] + Cnt2[i];
		if(MAX < sum)
			MAX = sum;
	}
}

int main(){
	scanf("%d",&N);
	N = N+1;
	A[0] = Cnt[0] = Cnt2[N] = 0;
	for(int i=1; i<N; i++)
		scanf("%d",&A[i]);

	find();

	printf("%d\n",MAX-1);
}

복잡도

$O(N^{2})$
n은 1~N x 각각 n일때 n-1만큼 비교 = $O({N(N-1) \over 2}) = O(N^{2})$