[백준] 알고리즘 11054번 - 가장 긴 바이토닉 부분 수열 문제

#include<bits/stdc++.h>
using namespace std;
int dp[1001];
int dp1[1001];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	vector<int> v1(n);
	for (int i = 0; i < n; i++) {
		cin >> v1[i];
	}
	int ans = 0;
	 
	for (int i = 0; i < n; i++) {
		dp[i] = 1;

		for (int j = 0; j < i; j++) {
			if (v1[j] < v1[i]) {  
				dp[i] = max(dp[i],  dp[j]+1);
			}
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		dp1[i] = 1;
		for (int j = i + 1; j < n; j++) {
			if (v1[j] < v1[i]) {  
				dp1[i] = max(dp1[i], dp1[j] + 1);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		ans = max(ans, dp[i] + dp1[i] - 1);
	}
	cout << ans;
}

 

오름 순과 내림 순을 구해서 더한 후, 자기자신이 중복되는 값 1개를 빼준다. 

중복 -> ( 1 2 3 2 1)

증가하는 수열은 1,2,3

감소하는 수열은 3,2,1 로 3이 중복되므로 한개를 빼줘야한다.

 

배열 예시를 앞에서 보면, 증가하는 수열을 구한 후 감소하는 수열을 구해줘야 한다.

즉, 0부터 시작하는건 증가하는 수열 , n-1번부터 시작하여 뒤로도 증가하는 수열을 구해주면

앞에서 보면 n-1 구한 값은 감소하는 수열로 생각하면된다.