(c++)백준 11504번: 가장 긴 바이토닉 부분 수열

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

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

두 개의 dp배열이 필요하다. 하나는 각각 숫자들의 앞에서 증가 수열의 길이를 저장하는 dp_front, 다른 하나는 각각 숫자들의 뒤에서 감소 수열의 길이를 저장하는 dp_back으로 했다.

 

dp_front[i] : i를 마지막 숫자로 했을 때 가장 긴 증가 부분 수열

dp_back[i] : i를 시작 숫자로 했을 때 가장 긴 감소 부분 수열

 

모두 구하고, 인덱스마다 dp_front[x] + dp_back[x] - 1 (같은 숫자 A[i]를 두번 세게 되므로 -1을 꼭 해줘야 한다)를 하여 그 결과값이 가장 큰 것을 출력한다.

 

 

#include <iostream>
using namespace std;

int N;
int A[1001];
long long dp_front[1001];//증가부분수열
long long dp_back[1001];//감소부분수열

void DP() {
	long long Max = -1;
	
	//증가부분수열(해당 인덱스를 마지막으로 하는 수열)

	//모두 1로 초기화
	for (int i = 1; i <= N; i++) {
		dp_front[i] = 1;
	}

	for (int i = 2; i <= N; i++) {
		long long maxLength = 0;
		for (int j = i - 1; j >= 1; j--) {
			//자신보다 더 작은 값 나타나면 그 값을 처음으로 했을 때 
			//가장 긴 부분 수열 길이를 더하기 (여러개면 부분 수열 길이가 가장 긴 것 더하기)
			if (A[i] > A[j] && maxLength < dp_front[j]) {
				maxLength = dp_front[j];
			}
		}
		dp_front[i] += maxLength;
	}

	//감소부분수열(해당 인덱스를 시작으로 하는 수열)
	
	//모두 1로 초기화
	for (int i = 1; i <= N; i++) {
		dp_back[i] = 1;
	}

	for (int i = N-1; i >= 1; i--) {
		long long maxLength = 0;
		for (int j = i + 1; j <= N; j++) {
			//자신보다 더 작은 값 나타나면 그 값을 처음으로 했을 때 
			//가장 긴 부분 수열 길이를 더하기 (여러개면 부분 수열 길이가 가장 긴 것 더하기)
			if (A[i] > A[j] && maxLength < dp_back[j]) {
				maxLength = dp_back[j];
			}
		}
		dp_back[i] += maxLength;
	}

	long long tmp = 0;
	for (int i = 1; i <= N; i++) {
		tmp = dp_back[i] + dp_front[i] - 1;
		if (Max < tmp)
			Max = tmp;
	}
	cout << Max << endl;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	DP();
	return 0;
}