[백준][DP] 가장 긴 바이토닉 부분수열

1. 문제 주소

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

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

2. 문제

i번째 수까지 가장 긴 증가하는 부분 수열을 구한 후 i번째 수부터 가장 긴 감소하는 부분 수열을 구하면 된다. 이때 i번째 숫자는 2번 카운팅 되기 때문에 -1을 해주어야 한다.

3. 소스코드

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    vector<int> increase_num(n);
    vector<int> decrease_num(n);
 
    for (int i = 0; i < n; i++) {
        increase_num[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j]<a[i] && increase_num[i] == increase_num[j]) {
                increase_num[i] = increase_num[j] + 1;
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        decrease_num[i] = 1;
        for (int j = n - 1; j > i; j--) {
            if (a[i] > a[j] && decrease_num[i] == decrease_num[j])
                decrease_num[i] = decrease_num[j] + 1;
        }
    }
 
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (result < increase_num[i] + decrease_num[i] - 1)
            result = increase_num[i] + decrease_num[i] - 1;
    }
    cout << result << '\n';
    return 0;
}