[BOJ]백준 11054번: 가장 긴 바이토닉 수열/DP

www.acmicpc.net/problem/11054

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

바이토닉 부분수열은 가장 긴 증가+감소 수열을 섞은 문제이다

맨 앞부터 가장 긴 증가 수열을 구하고, 맨 뒤부터 가장 긴 증가 수열을 구하면 i번째 원소에 대해 (현재 원소를 포함하는 가장 긴 증가 수열의 길이, 현재 원소를 포함하는(맨 뒤부터) 가장 긴 감소 수열의 길이)를 구할 수 있다

for문을 두번 돌아준 뒤 해당 값들의 합이 가장 큰 쌍을 찾아주면 되는 문제

#include <cstdio>
int n,dp[3][1001],ans;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &dp[0][i]);
		dp[1][i] = 1;
		for (int j = 0; j < i; j++)
			if (dp[0][j] < dp[0][i]
				&& (dp[1][j] + 1 > dp[1][i]))
				dp[1][i] = dp[1][j] + 1;
	}
	for (int i = n-1; i >=0; i--) {
		dp[2][i] = 1;
		for (int j = n-1; j > i; j--)
			if (dp[0][j] < dp[0][i]
				&& (dp[2][j] + 1 > dp[2][i]))
				dp[2][i] = dp[2][j] + 1;
		if (dp[1][i] + dp[2][i] > ans)
			ans = dp[1][i] + dp[2][i];
	}
	printf("%d", ans - 1);
	return 0;
}