题解 | #合唱队#

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n, temp;
    vector<int> data;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        data.push_back(temp);
    }
    //初始数组
    int left [3000] = {0};
    int right[3000] = {0};
    //左边
    for (int i = 0; i < data.size(); i++) {
        left[i] = 1;
        for (int j = 0; j < i; j++) {
            if (data[j] < data[i] && left[j] + 1 > left[i]) {
                left[i] = left[j] + 1; 
            }
        }
    }
    //右边
    for (int i = data.size() - 1; i > 0; i--) {
        right[i] = 1;
        for (int j = data.size() - 1 ; j > i; j--) {
            if (data[j] < data[i] && right[j] + 1 > right[i]) {
                right[i] = right[j] + 1; 
            }
        }
    }
    //计算差距
    int min = n;
    for (int i = 0; i < n; i++) {
        if (n - left[i] - right[i] + 1 < min)
            min = n - left[i] - right[i] + 1;
    }
    cout << min << endl;
}