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

 

 

 

LIS와 LDS 를 구해 가장 긴 바이토닉  부분 수열을 구하는 문제.

 

문제의 핵심은 LIS + LDS - 1 값을 찾는 것인데, 간단하게 생각해서 왼쪽에서부터 LIS 를 찾고, 오른쪽에서부터 LIS 를 찾아 더한 후 -1을 해주면 되는 것이다.

 

각 LIS 를 구한 후 두 개의 dp 벡터에서 해당 인덱스를 넣었을 때 최대 값이 되는 dp_inc + dp_dec 값을 찾아서 출력했다.

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MOD 10007

int main() {
    vector<int> a(1001, 0);
    vector<int> dp_inc(1001, 1);
    vector<int> dp_dec(1001, 1);

    int N;

    cin >> N;

    for (int i = 1; i <= N; i++)
        cin >> a[i];

    int ans = 0;
    int ans_ind = 0;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (a[i] > a[j])
            {
                dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1);

            }
        }
    }

	// 역순 LIS 찾기

    for (int i = N; i >= 1; i--)
    {
        for (int j = N; j >= i; j--)
        {
            if (a[i] > a[j])
            {
                dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1);

            }

        }
    }

    int max_length = 0;

    for (int i = 1; i <= N; i++)
    {
        max_length = max(max_length, dp_inc[i] + dp_dec[i] - 1);
    }

    cout << max_length;

    return 0;
}