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

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

이 문제의 핵심은 증가하는 하는 부분에서 감소하는 부분을

잘 체크하는 것이었다.

N의 범위가 1000이어서 O(N^2)으로 시도해보았다.

수열의 원소 하나당 그 전 원소들을 모두 탐색하며 dp테이블에 메모이제이션했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define FASTIO ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define MAX 1000+1
using namespace std;

int idp[MAX];
int ddp[MAX];
int n;
int arr[MAX];
int j;
int main(){
	FASTIO
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	
	for(int i=0;i<n;i++){
		idp[i]=1;
		ddp[i]=1;
		for(int j=0;j<=i;j++){
			if(arr[j]<arr[i]){
				idp[i]=max(idp[i],idp[j]+1);
			}
			else if(arr[j]>arr[i]){
				ddp[i]=max(idp[j]+1,max(ddp[j]+1,ddp[i]));
			}
		}
	}
	sort(idp,idp+n);
	sort(ddp,ddp+n);
	cout << max(idp[n-1],ddp[n-1]);
}