(C++) - 백준(BOJ) 11054번 : 가장 긴 바이토닉 부분 수열

//3가지 경우가 있다.
//1.배열의 끝까지 증가하는 경우
//2.배열의 끝까지 감소하는 경우
//3.배열이 증가하다가 기준값을 담고 있는 인덱스 이후부터 감소하는 경우
 
//이 모두를 포함하는 방법은 가장 긴 증가하는 부분수열을 인덱스 양쪽 끝에서 시작해서 각자 구한다음
//그 두 배열의 합 중 가장 큰 값이 최대 바이토닉 수열의 길이가 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    int ans = 0;
    cin >> n;
    int *a = new int[n + 1];
    int *d = new int[n + 1];
    int *d2 = new int[n + 1];
 
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        d[i] = 1;
        for (int j = 1; j <= i; j++)
        {
            if (a[j]<a[i] && d[j] + 1 > d[i])
            {
                d[i] = d[j] + 1;
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        d2[n - i + 1] = 1;
        for (int j = 1; j <= i; j++)
        {
            if (a[n - j + 1]<a[n - i + 1] && d2[n - j + 1] + 1 > d2[n - i + 1])
            {
                d2[n - i + 1] = d2[n - j + 1] + 1;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (ans < (d[i] + d2[i]))
        {
            ans = d[i] + d2[i];
        }
    }
    cout << ans-1 << '\n';
}