c++ 백준_11054_"가장 긴 바이토닉 부분 수열"

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

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

 

입력 크기가 크지 않아서

N^2 복잡도가 걸리는 DP 방식을 사용해

각 요소 마다 가장 긴 부분 수열의 길이를 저장했다.

​

올라갔다가 감소하는 형태니까 결국에는

한번은 앞에서 증가하는 부분 수열을 찾고

한번은 뒤에서 증가하는 부분 수열을 찾으면 되었다.

​

그래서 구한 각각의 가장 긴 부분 수열의 길이가 저장된 배열 2개의

같은 index끼리의 합이 가장 큰 것을 반환하였다.

​

그리고 가장 긴 부분 수열이 중첩돼서 하나가 포함되니까

1을 빼주었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int A[1000];
int INCRE_DP[1000];
int DECRE_DP[1000];
int main(void) {

	int N;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int len = 0;

	for (int i = 0; i < N; i++) {
		int now = 0;
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j])
				now = max(now, INCRE_DP[j]);
		}
		INCRE_DP[i] = now + 1;
	}

	for (int i = N - 1; i >= 0; i--) {
		int now = 0;
		for (int j = N - 1; j > i; j--) {
			if (A[i] > A[j])
				now = max(now, DECRE_DP[j]);
		}
		DECRE_DP[i] = now + 1;
	}

	
	for (int i = 0; i < N; i++) {
		len = max(len, DECRE_DP[i] + INCRE_DP[i]);
	}

	cout << len - 1;
}