[c++] 11054 가장 긴 바이토닉 부분 수열 (이분탐색)

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

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

앞에서부터 가장 긴 부분수열 사이즈 찾아서 배열에 넣고,

뒤에서부터 사이즈 찾아서 넣고 더한 값 중에서 가장 큰 값을 찾았다.

중복값이 만날 때 발생하니까 하나 빼주기

 

생각해보니 dp가 아니라 이분탐색으로 풀었다. lower_bound 찾아서 했으니 흠 🧐

 

전체 코드

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

int N, arr[1000], dp_bottomUp[1000], dp_topDown[1000];
vector<int> lis;

int main(int argc, const char * argv[]) {
    cin >> N;
    for (int i=0; i<N; i++) {
        cin >> arr[i];
    }
    
    for (int i=0; i<N; i++) {
        if (lis.empty()) {
            lis.push_back(arr[i]);
        }
        else if (lis.back() < arr[i]) {
            lis.push_back(arr[i]);
        }
        else {
            int idx = (int)(lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin());
            lis[idx] = arr[i];
        }
        dp_bottomUp[i] = (int)lis.size();
    }
    lis.clear();
    
    for (int i=N-1; i>=0; i--) {
        if (lis.empty()) {
            lis.push_back(arr[i]);
        }
        else if (lis.back() < arr[i]) {
            lis.push_back(arr[i]);
        }
        else {
            int idx = (int)(lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin());
            lis[idx] = arr[i];
        }
        dp_topDown[i] = (int)lis.size();
    }
    
    vector<int> res;
    for (int i=0; i<N; i++) {
        res.push_back(dp_bottomUp[i] + dp_topDown[i]);
    }
    sort(res.begin(), res.end());
    
    cout << res.back()-1 << "\n";

    return 0;
}