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

문제

풀이

• 바이토닉 부분 수열의 가운데 값을 찾는 것으로 생각하는게 쉽다. 
• 수열의 앞에서부터 탐색하여 증가하는 값을 cache로 두고, 마찬가지로 뒤에서 부터 탐색하여 증가하는 값을 cache_reverse로 둔다.
• cache와 cache_reverse의 합이 최대가 되는 인덱스를 찾는다.

코드

 

#include <iostream>

using namespace std;

int main()
{
    int N;
    int A[1001];

    cin >> N;

    for (int i = 1; i <= N; ++i)
    {
        cin >> A[i];
    }

    if (N == 1)
    {
        cout << "1";
        return 0;
    }

    int cache[1001];
    int cache_reverse[1001];

    // 증가하는 부분 수열
    for (int i = 1; i <= N; ++i)
    {
        cache[i] = 1;
        int maxi = 0;
        for (int j = 1; j <= i; ++j)
        {
            if (A[i] > A[j])
            {
                maxi = max(maxi, cache[j]);
            }
        }

        cache[i] = maxi + 1;
    }

    // 뒤에서 부터 탐색하여 증가하는 부분 수열
    for (int i = N; i >= 1; --i)
    {
        cache_reverse[i] = 1;
        int maxi = 0;
        for (int j = N; j >= i; --j)
        {
            if (A[i] > A[j])
            {
                maxi = max(maxi, cache_reverse[j]);
            }
        }

        cache_reverse[i] = maxi + 1;
    }

    // 가장 긴 바이토닉의 부분 수열의 가운데 값을 찾는 과정
    int answer = 0;
    for (int i = 1; i <= N; ++i)
    {
        answer = max(answer, cache[i] + cache_reverse[i] - 1);
    }

    cout << answer;

    return 0;
}