<Baekjoon>#11054 가장 긴 바이토닉 부분 수열 (Longest bitonic subsequence) c++

문제에서 주어진 대로 바이토닉 부분 수열은 수열 A가 주어졌을 때 A[i]값을 기준으로 A[0]에서 A[i-1]중 증가하는 부분 수열이 존재하고, A[i+1]에서 A[N]중 감소하는 부분 수열이 존재하는 경우를 말한다.

'가장 긴 증가하는 부분 수열' 알고리즘과 '가장 긴 감소하는 부분 수열' 알고리즘을 적당히 조합해보면 답이 나온다.

주의 할 점은,
dp (가장 긴 증가하는 부분 수열의 갯수)와 rdp (가장 긴 감소하는 부분 수열의 갯수) 각각의 최댓값을 더해준 후 -1을 해주어야 한다.
같은 값이 2번 counting 되기 때문!

**참고로 앞에서 한 포스팅의 알고리즘과 변수명이나 반복문의 범위 등이 조금씩 다른데 같은 알고리즘이지만 ctrl+c, ctrl+v 하지 않고 할 때마다 조금 더 직관적이고 깔끔한 코드를 찾기 위해 나름대로 고군분투중..!

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int MAX = 1001;

int bitonic(const vector<int>& A, int k) {
	int dp[MAX];
	int rdp[MAX];
	dp[0] = rdp[k-1]=1; 

	for (int i = 1; i <k; i++) {
		dp[i] = 1;
		
		for (int j = 0; j <i; j++) {
			if (A[i] > A[j] && dp[i] < dp[j] + 1)
				dp[i] = dp[j] + 1;
		}
	}

	for (int i = k - 2; i >= 0;  i--) {
		rdp[i] = 1;

		for (int j = k - 1; j >i; j--) {
			if (A[i] > A[j] && rdp[i] < rdp[j] + 1)
				rdp[i] = rdp[j] + 1;
		}
	}
	
	int result=0;
	for (int i = 0; i < k; i++) {
		result = max(result, (dp[i] + rdp[i]) - 1);
	}
	return result;
}

int main() {

	int k;
	cin >> k;

	if (k > MAX)
		exit(EXIT_FAILURE);

	vector<int>A(k);

	for (int i = 0; i < k; i++)
		cin >> A[i];

	cout << bitonic(A, k) << endl;

	return 0;
}