3장 다이나믹 프로그래밍 - (4) 문제 풀이 4 [11054번 - 가장 긴 바이토닉 부분 수열]

D[i] : a[i]를 마지막에 포함하는 가장 긴 증가하는 부분 수열의 길이

d[i] : a[i]를 시작으로 포함하는 가장 긴 감소하는 부분 수열의 길이

정답 : max(D[i]+d[i]-1), 1<=i<=n

#include <iostream>

using namespace std;

int D[1001];

int d[1001];

int a[1001];

int main(void) {

int n;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

/*

D[i] : a[i]를 마지막에 포함하는 가장 긴 증가하는 부분 수열의 길이

d[i] : a[i]를 시작으로 포함하는 가장 긴 감소하는 부분 수열의 길이

정답 : max(D[i] + d[i] - 1), 1 <= i <= n

*/

// D[i] 구하기

for (int i = 1; i <= n; i++) {

D[i] = 1;

for (int j = 1; j < i; j++) {

if (a[j] < a[i] && D[i] < D[j] + 1) {

D[i] = D[j] + 1;

}

}

}

// d[i] 구하기

for (int i = n; i >= 1; i--) {

d[i] = 1;

for (int j = i + 1; j <= n; j++) {

if (a[j] < a[i] && d[i] < d[j] + 1) {

d[i] = d[j] + 1;

}

}

}

int max = 0;

for (int i = 1; i <= n; i++) {

if (max < D[i] + d[i] -1) {

max = D[i] + d[i] - 1;

}

}

cout << max << endl;

return 0;

}