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

가장 긴 바이토닉 부분 수열 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	7732	4072	3295	54.167%

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1 

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1 

7

     

 문제 풀이

1차 풀이 (  2120 KB,  12 ms)

바이토닉 부분 수열에는 최댓값이 존재한다.

최댓값을 고정시키고,  

그 최댓값을 끝으로 하는 최장 증가 부분수열과

그 최댓값을 첫으로 하는 최장 감소 부분수열을 구한 뒤,

그 둘을 더하고 1을 뺀다.  

최댓값이 각 부분수열에서 중복되기 때문이다. 

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

int N, val;
unsigned long ans = 0;
vector<int> A, in, de;

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        cin >> N;
        for(int i=0; i<N; i++) {
                cin >> val;
                A.emplace_back(val);
        }

        for(int fix=0; fix<N; fix++){
                //! init.
                in.clear();
                de.clear();

                //! inc.
                for(int i=0; i<=fix; i++){
                        int where_to_insert = lower_bound(in.begin(), in.begin()+in.size(), A[i]) - in.begin();
                        if(where_to_insert == in.size()) in.push_back(A[i]);
                        else in[where_to_insert] = A[i];
                }

                //! dec.
                for(int i=fix; i<N; i++){
                        int where_to_insert = lower_bound(de.begin(), de.begin()+de.size(), A[i], greater<>()) - de.begin();
                        if(where_to_insert == de.size()) de.push_back(A[i]);
                        else de[where_to_insert] = A[i];
                }

                //! update ans.
                ans = max(ans, in.size() + de.size() - 1);
        }
        cout << ans;
}