백준 11054 c++ : DP, LIS, LDS

LIS와 LDS를 구하는 알고리즘을 이용해 바이토닉을 구할 수 있다.
각각 DP로 LIS와 LDS를 구하고, 바이토닉 = LIS[i] + LDS[i] - 1 을 통해 최대 바이토닉 수열 길이를 구할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

void input_data(int* N, vector<int>& A) {
	cout << "input_data()\n";
	
	int i, Ai;

	cin >> *N;
	for (i = 0; i < *N; i++) {
		cin >> Ai;
		A.push_back(Ai);
	}

	return;
}

int find_answer(int N, vector<int>& A) {
	cout << "find_answer()\n";

	int answer = 0;
	int i, j, max_length = 0, current;
	vector<int> LIS(N, 1);
	vector<int> LDS(N, 1);

	//바이토닉을 구하는 방법
	//      1 5 2 1 4 3 4 5 2 1 이 입력된 경우
	//LIS는 1 2 2 1 3 3 4 5 2 1  5개
	//LDS는 1 5 2 1 4 3 3 3 2 1  5개
	//BIT는 1 6 3 1 6 5 6 7 3 1  7개
	
	//바이토닉 최대 길이는 1 2 3 4 5 2 1 
	//LIS[i] + LDS[i] - 1

	//왼쪽부터 LIS
	for (i = 1; i < N; i++) {
		for (j = 0; j < i; j++) {
			if (A[j] < A[i]) {
				LIS[i] = max(LIS[i], LIS[j] + 1);
			}
		}
	}
	cout << "LIS : ";
	for (int temp : LIS) {
		cout << temp << " ";
	}
	cout << "\n";

	//오른쪽부터 LIS == LDS
	for (i = N - 2; i >= 0; i--) {
		for (j = N - 1; j > i; j--) {
			if (A[j] < A[i]) {
				LDS[i] = max(LDS[i], LDS[j] + 1);
			}
		}
	}
	cout << "LDS : ";
	for (int temp : LDS) {
		cout << temp << " ";
	}
	cout << "\n\n";

	//최대 바이토닉을 구하려면?
	//LIS[i] + LDS[i] + 1이 최대인 경우를 찾아야 함
	for (i = 0; i < N; i++) {
		current = LIS[i] + LDS[i] - 1;
		cout << current << " = " << LIS[i] << " + " << LDS[i] << " - 1\n";
		max_length = max(max_length, current);
	}
	answer = max_length;

	return answer;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	vector<int> A;

	input_data(&N, A);
	cout << find_answer(N, A) << "\n";

	return 0;
}