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

#include <stdio.h>
 
int arr[1005] = { 0 };
int maxDP[1005] = { 0 };
int minDP[1005] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= n; i++) {
        int maxN = 0;
        for (int k = 1; k < i; k++) {
            if (arr[k] < arr[i]) {
                if (maxN < maxDP[k]) {
                    maxN = maxDP[k];
                }
            }
        }
        maxDP[i] = maxN + 1;
    }
    
    for (int i = n; i >= 1; i--) {
        int maxN = 0;
        for (int j = n; i < j; j--) {
            if (arr[i] > arr[j]) {
                if (maxN < minDP[j]) {
                    maxN = minDP[j];
                }
            }
        }
        minDP[i] = maxN + 1;
    }
 
    int maxRst = 0;
    for (int i = 1; i <= n; i++) {
        if (maxRst < minDP[i] + maxDP[i]) {
            maxRst = minDP[i] + maxDP[i];
        }
    }
    printf("%d", maxRst - 1);
}