[BAE/<JOON> 문제풀이] 11054. 가장 긴 바이토닉 부분 수열 (DP.030)

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

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

최장 증가 부분 수열을 앞뒤로 찾아서 합쳤을 때 가장 큰 위치를 찾아 -1 하면 된다.

 

(2개 수열에 현재 위치 숫자가 2번들어가므로)

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    vector<int> arr;
    vector<int> dp1, dp2;

    cin >> n;
    arr.resize(n + 1);
    dp1.resize(n + 1);
    dp2.resize(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp1[i] = 1;
        dp2[i] = 1;
    }
    dp1[0] = 0;
    dp2[n + 1] = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp1[i] = dp1[i] > dp1[j] + 1 ? dp1[i] : dp1[j] + 1;
            }
        }        
    }

    for (int i = n - 1; i >= 1; i--) {
        for (int j = n; j >= i + 1; j--) {
            if (arr[i] > arr[j]) {
                dp2[i] = dp2[i] > dp2[j] + 1 ? dp2[i] : dp2[j] + 1;
            }
        }
    } 
    int mx = -1;
    for (int i = 1; i <= n; i++) {
        if (mx < dp1[i] + dp2[i] - 1) {
            mx = dp1[i] + dp2[i] - 1;
        }
    }

    cout << mx;

    /*for (auto d1 : dp1) {
        if (d1 == 0) continue;
        cout << d1 << " ";
    }
    cout << "\n";
    for (auto d2 : dp2) {
        if (d2 == 0) continue;
        cout << d2 << " ";
    }*/
    return 0;
}