가장 긴 바이토닉 부분 수열

문제 링크

발상

어떤 인덱스 $i$를 골랐을 때 양쪽 방향으로 모두 감소하는 수열 중 가장 긴 부분 수열을 찾아내는 문제다. 딱 봐도 LIS 문제의 바리에이션인게 보인다. 가장 긴 바이토닉 부분 수열의 길이는 어떤 인덱스 $i$의 양쪽으로의 LIS길이를 더하고 1을 뺀 값이다. 양쪽으로의 LIS길이에 모두 현재 인덱스 $i$가 포함되어 있기 때문에 중복된 인덱스를 제거해야 한다.

점화식

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n; cin >> n; vector<int> arr(n + 1), dp1(n + 1, 1), dp2(n + 1, 1);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	int mx = 0;
	
	// 정방향 LIS
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j] && dp1[j] + 1 > dp1[i]) {
				dp1[i] = dp1[j] + 1;
			}
		}
	}
 
	// 역박향 LIS
	for (int i = n - 1; i >= 1; i--) {
		for (int j = n; j > i; j--) {
			if (arr[i] > arr[j] && dp2[j] + 1 > dp2[i]) {
				dp2[i] = dp2[j] + 1;
			}
		}	
	}
	
	for (int i = 1; i <= n; i++) {
		int s = dp1[i] + dp2[i] - 1; // 현재 인덱스 i가 2번 counting 되었으므로 -1 해야함 
		mx = mx > s ? mx : s;
	}
	cout << mx;
	return 0;
}