题解 | 合唱队形

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    int dp_l[n];
    int dp_r[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        dp_r[i] = dp_l[i] = 1;
    }
    //计算左侧最长递增子序列
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp_l[i] = dp_l[i] > dp_l[j] + 1 ? dp_l[i] : dp_l[j] + 1;
            }
        }
    }
    //计算右侧最长递减子序列
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                dp_r[i] = dp_r[j] + 1 > dp_r[i] ? dp_r[j] + 1 : dp_r[i];
            }
        }
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (dp_r[i] + dp_l[i] > max) {
            max = dp_l[i] + dp_r[i] - 1;
        }
    }
    printf("%d", n - max);
    return 0;
}