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

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

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

---

• 바이토닉 부분 수열은, 증가하는 부분 수열과 감소하는 부분 수열이 합쳐진 개념이다.
• 가장 긴 바이토닉 부분 수열의 길이를 구하기 위해서는, 위의 두 수열이 각각 갖는 최댓값을 인덱스별로 구해놓은 뒤, 가장 합이 높은 값을 구하면 된다.
• 두 문제를 이미 풀었다면 어렵지 않게 풀 수 있다.
• https://bconfiden2.tistory.com/272 (가장 긴 감소하는 부분 수열)
• https://bconfiden2.tistory.com/161 (가장 긴 증가하는 부분 수열)

---

#include <iostream>

using namespace std;

int N;
int values[1000];
int fleft[1000];
int fright[1000];

int main(void)
{
    cin >> N;
    for(int i = 0 ; i < N ; i++)
    {
        fleft[i] = fright[i] = 1;
        cin >> values[i];
    }

    for(int i = 0 ; i < N ; i++)        // 가장 긴 증가하는 부분 수열
    {
        int maxi = 1;
        for(int k = 0 ; k < i ; k++)
        {
            if(values[k] < values[i])
            {
                if(fleft[k] + 1 > maxi) maxi = fleft[k] + 1;
            }
        }
        fleft[i] = maxi;
    }

    for(int i = N-1 ; i >= 0 ; i--)     // 가장 긴 감소하는 부분 수열
    {
        int maxi = 1;
        for(int k = N-1 ; k > i ; k--)
        {
            if(values[k] < values[i])
            {
                if(fright[k] + 1 > maxi) maxi = fright[k] + 1;
            }
        }
        fright[i] = maxi;
    }

    int answer = 0;
    for(int i = 0 ; i < N ; i++)        // 두 수열의 합 중 최댓값이 가장 긴 바이토닉 수열
    {
        if(fleft[i] + fright[i] > answer)
        {
            answer = fleft[i] + fright[i];
        }
    }
    cout << answer - 1 << endl;
}