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

문제

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

설명

1. 여기서는 lower_bound 풀이를 사용했다 여기서 가장 긴 증가하는부분수열을 앞에서1번, 뒤에서 1번 했다 끝.

2. 여기서 주의할 점 if (!v.empty() && v.back() < arr[i]) v.push_back(arr[i]); 이런식으로 처음에 했었는데 안된다 왜냐? 비어있을 경우도 처리해야하니 이렇게 하면 자꾸 로직이 꼬이게된다

3. 2번의 문제를 해결하고자 단순하게 로워바운드로 찾은 위치에 대해서만 if else로 처리해주면된다 .size()랑 로워바운드 위치가 같다면 .push_back으로 넣어준다 왜냐? (arr[i]가 더큰 값이니, 여기서 .size()랑 위치를 비교하는 것만으로도 empty()까지 처리할 수 있어서 좋다)

소스

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[2000];
vector<int> v;
int foward[2000];
int back[2000];
int ans;
int main() {

    cin >> n;


    for (int i = 0; i < n; i++)    cin >> arr[i];


    for (int i = 0; i < n; i++)
    {
    /*    if (v.empty()) {
            v.push_back(arr[i]);
            continue;
            넣고 continue 하면 밑에 back[i]에는 값을 넣지 못한다...
        }*/
        int tmp = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();

        // if (!v.empty() && v.back() < arr[i]) v.push_back(arr[i]); 비어있을 경우도 처리 
        if (v.size() == tmp) v.push_back(arr[i]);
        else v[tmp] = arr[i];
        foward[i] = tmp + 1;
    }
    v.clear();
    for (int i = n - 1; i >= 0; i--) {
        int tmp = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
        /*if (v.empty()) {
            v.push_back(arr[i]);
            continue;
            넣고 continue 하면 밑에 back[i]에는 값을 넣지 못한다... 
        }*/

        //if (!v.empty() && v.back() < arr[i]) v.push_back(arr[i]);
        if (v.size() == tmp) v.push_back(arr[i]);
        else v[tmp] = arr[i];
        back[i] = tmp + 1;
    }

    for (int i = 0; i < n; i++) {
        ans = max(ans, foward[i] + back[i] - 1);
    }
    cout << ans;
    return 0;
}