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

문제

https://www.acmicpc.net/problem/11054
증가하다가 감소하는 형태의 수열의 최장 길이를 구하는 문제다.
증가만 하거나 감소만 해도된다.

풀이

2개의 dp 배열을 두고
왼쪽에서부터 가장 긴 증가하는 부분 수열의 개수를 구하고
오른쪽에서부터 가장 긴 증가하는 부분 수열의 개수를 구한다.

두 배열의 각 index에서의 합을 구했을 때 최대값이 정답이 된다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1001], l[1001], r[1001], ret;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
        
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i])
                l[i] = max(l[i], l[j]);
        }
        l[i] += 1;
    }
    
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[i])
                r[i] = max(r[i], r[j]);
        }
        r[i] += 1;
    }
    
    for (int i = 0; i < n; i++)
        ret = max(ret, l[i] + r[i]);
    cout << ret - 1 << "\n";
}```