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

문제 링크 : www.acmicpc.net/problem/11054

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

최장 증가 수열(LIS)에 대해 숙지하고 있다면 쉽게 해결할 수 있는 문제이다.

전체 수열의 크기가 1000으로 작기 때문에 O(N^2)의 시간복잡도를 갖는 DP를 사용할 수 있다.

수열의 한 수에 대해, 왼쪽 끝에서 그 수에서 끝나는 LIS와 오른쪽 끝에서 시작해 그 수에서 끝나는 LIS 길이의 합(-1)이 곧 바이토닉 수열의 길이가 된다.

(이 때, 원래의 수는 그 바이토닉 부분 수열에서 가장 큰 값이 된다.)

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
 
int n;
int arr[1001], asc[1001], desc[1001];
 
void dp_asc() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) asc[i] = max(asc[i], asc[j] + 1);
        }
    }
}
 
void dp_desc() {
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) desc[i] = max(desc[i], desc[j] + 1);
        }
    }
}
 
void init() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        asc[i] = 1;
        //desc[i] = 1;
    }
 }
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    dp_asc();
    dp_desc();
 
    int answer = 0;
    for (int i = 0; i < n; i++) {
        answer = max(answer, asc[i] + desc[i]);
    }
 
    printf("%d\n", answer);
 
    //system("PAUSE");
    return 0;
}