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

이 문제는 다이나믹 프로그래밍 문제이다.

 

이 문제는 LIS 문제를 두 번 쓴 다음에 합치면 되는 간단한 문제이다.

 

dp1[i] : i를 마지막으로 하는 가장 긴 증가하는 부분 수열 (왼쪽 기준)

dp2[i] : i를 마지막으로 하는 가장 긴 감소하는 부분 수열 (오른쪽 기준)

 

으로 세우고 마지막에 각 인덱스 i에 대해 이를 합친 결과 중 가장 긴 것을 답으로 내면 정답이 나온다.

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

#define MAX 1000

int N;
int arr[MAX];
int dp1[MAX];
int dp2[MAX];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	for (int i = 0; i < N; i++) {
		int present = arr[i];
		int longest = 0;

		for (int j = 0; j < i; j++) {
			int prev = arr[j];

			if (prev < present) {
				if (dp1[j] > longest) {
					longest = dp1[j];
				}
			}
		}

		dp1[i] = longest + 1;
	}

	for (int i = N - 1; i >= 0; i--) {
		int present = arr[i];
		int longest = 0;

		for (int j = N - 1; j >= i + 1; j--) {
			int right = arr[j];

			if (present > right) {
				if (dp2[j] > longest) {
					longest = dp2[j];
				}
			}
		}
		dp2[i] = longest + 1;
	}

	int answer = -1;
	for (int i = 0; i < N; i++) {
		int result = dp1[i] + dp2[i] - 1;
		answer = max(answer, result);
	}
	cout << answer << '\n';
	
	return 0;
}