[#11054] 가장 긴 바이토닉 부분 수열

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
vector<int> dp;  //정방향 수열의 LIS
vector<int> reverseDp;  //역방향 수열의 LIS
vector<int> numbers;
 
void LIS(const int n, vector<int> funcNumbers, vector<int>& funcDp) {
    for (int i = 1; i < n; i++) {
        int maxVal = 0;
        for (int j = 0; j < n - 1; j++) {
            if (funcNumbers[j] < funcNumbers[i]) {
                maxVal = max(maxVal, funcDp[j]);
            }
        }
        funcDp[i] = maxVal + 1;
    }
}
 
int main() {
    int n;
    cin >> n;
 
    dp = vector<int>(n, 0);
    reverseDp = vector<int>(n, 0);
    numbers = vector<int>(n, 0);
 
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }
 
    dp[0] = 1;
    reverseDp[0] = 1;
 
    LIS(n, numbers, dp);  //정방향 LIS 구하기
 
    reverse(numbers.begin(), numbers.end());
    LIS(n, numbers, reverseDp);  //역방향 LIS 구하기
 
    int maxVal = INT_MIN;
    for (int i = 0; i < n; i++) {
        maxVal = max(maxVal, dp[i] + reverseDp[n - 1 - i]);
    }
 
    cout << maxVal - 1;  //한개가 두 번 더해졌기 때문에 1 빼주기
 
    return 0;
}

 

11053 LIS 문제 응용

 

수열이 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 

1   5   2   1   4   3   4  5   2  1 이면    [7]을 기준으로 한게 답이다.

---------------------------> LIS(1)

                       LIS(2) <---------

 

number 정방향으로 LIS 한번 구하고 reverse 시켜서 또 LIS 구하고

각 LIS를 구한 결과 dp에서 LIS1[i] + LIS2[n-1-i] 가 최대가 되는 i가 기준 index

따라서 그 최댓값에서 i번째 수가 2번 들어갔으므로 1을 빼주면 된다.