LIS 알고리즘 사용하기 - 가장 긴 바이토닉 부분 수열

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

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

---

이 문제는 LIS 알고리즘을 사용하기 때문에 다이나믹 프로그래밍으로 분류되어 있습니다. 풀이 과정은 다음과 같습니다.

1. 왼쪽부터 오른쪽 방향으로 LIS 배열 계산
2. 오른쪽부터 왼쪽 방향으로 LIS 배열 계산
3. 각 포지션에서 두 배열을 더한 값에서 -1
4. 최댓값 반환

#include <iostream>
#include <cstdio>

using namespace std;
const int MAX_N = 1000;
int n;
int arr[MAX_N];

int solve() {
    int ret = 0;
    int a[n]; // 왼쪽에서 오른쪽으로 탐색하는 LIS 배열
    int b[n]; // 오른쪽에서 왼쪽으로 탐색하는 LIS 배열

    for(int i = 0; i < n; i++) {
        a[i] = b[i] = 1;
    }

    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[i] > arr[j] && a[i] < a[j] + 1) {
                a[i] = a[j] + 1;
            }

            if(arr[n - 1 - i] > arr[n - 1 - j] && b[n - 1 - i] < b[n - 1 - j] + 1) {
                b[n - 1 - i] = b[n - 1 - j] + 1;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        // 더한 LIS 값 -1 하고 최댓값 체크
        if(ret < a[i] + b[i] - 1) {
            ret = a[i] + b[i] - 1;
        }
    }

    return ret;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    cout << solve();
    return 0;
}