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

1 개요

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

• 백준 온라인 저지 11054번 문제
• BOJ 23단계

2 C++

#include <iostream>
using namespace std;

int N;
int A[1001];
int B[1001];
int C[1001];

void solve() {
    fill(B, B+1001, 1);
    fill(C, C+1001, 1);

    for(int i=1; i<=N; i++) {
        for(int j=1; j<i; j++) {
            if(A[j] < A[i]) {
                B[i] = max(B[i], B[j]+1);
            }
        }
    }

    for(int i=N; i>=1; i--) {
        for(int j=N; j>i; j--) {
            if(A[j] < A[i]) {
                C[i] = max(C[i], C[j]+1);
            }
        }
    }
    
    int ans = 0;
    for(int i=1; i<=N; i++) {
        if(B[i]+C[i] > ans) {
            ans = B[i]+C[i];
        }
    }
    cout << ans-1;
}

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> A[i];
    }
    solve();
}