백준 11054(가장 긴 바이오닉 부분 수열)

https://www.acmicpc.net/problem/11054

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

감소하다가 증가하지 않는 수열이 바이토닉 수열이라고 한다. 

 

그러니깐 증가만 해도 되고, 

감소만 해도 되고, 

증가하다가 감소해도 되고 

 

이 문제는 

어떤 수열이 주어졌을 그 수열의 부분수열 중 가장 긴 바이토닉 수열을 구하는 것이다. 

 

보자마자 생각나는 문제가 있다. LIS다 그런데 감소해야하는 경우도 구해야 한다. 

 

바이토닉 수열

dp[i] = max( i까지의 증가수열 + i부터 감소수열)

 

따라서 i까지의 증가수열과 i부터 감소수열 중 최대값을 구하자 

 

i까지의 증가수열 최댓값은 그냥 LIS다 

 

dp[i]는 뒤꽁무니 쫓아오는 값 중 그 값이 작은 값 중 dp의 최댓값 +1로 구할 수 있다. 

 

그러면 i부터 감소수열은? 

 

말장난이다. 증가나 감소나 똑같다. 선형이고 값만 살짝 바꿔주면 된다. 

 

이때 그냥 수열을 뒤집어서 LIS구하면 된다. 

 

그 뒤에 바이토닉 수열을 구하는 위 공식을 이용해서 답을 구할 수 있다. 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1001

int N, res=-1;
int seq[MAX];
int inc[MAX];
int decr[MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> seq[i];
	}
	for (int i = 0; i < N; i++) {
		inc[i] = 1;
		decr[i] = 1;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (seq[i] > seq[j]) {
				inc[i] = max(inc[i], inc[j] + 1);
			}
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		for (int j = N - 1; j > i; j--) {
			if (seq[i] > seq[j]) {
				decr[i] = max(decr[i], decr[j] + 1);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		res = max(res, inc[i] + decr[i]);
	}
	cout << res - 1 << "\n";
}