题解 | 合唱队形

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
	//分解两个最长子序列，从头，从尾；求对应下标元素和的最大值
    vector<int> dp_left(n, 1);
    vector<int> dp_right(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) dp_left[i] = max(dp_left[i], dp_left[j] + 1);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (nums[i] > nums[j]) dp_right[i] = max(dp_right[i], dp_right[j] + 1);
        }
    }

    int ans = n;
    for (int i = 0; i < n; i++) {
        ans = min(ans, n - (dp_left[i] + dp_right[i]) + 1);
    }
    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")