题解 | #合唱队#

#include <bits/stdc++.h>

using namespace std;

void process(vector<int> vec, int N, int& res){
    vector<int> leftNum(N, 0);
    vector<int> rightNum(N, 0);

    //左边的最长序列长度
    for(int i = 0; i < N; i++){
        for(int j = 0; j < i; j++){
            if(vec[j] < vec[i]){
                leftNum[i] = max(leftNum[i], leftNum[j]);
            }
        }
        leftNum[i] = leftNum[i] + 1;
        //cout << leftNum[i]<<endl;
    }
    
    //右边的最长序列长度
    for(int i = N - 1; i >= 0; i--){
        for(int j = N - 1; j > i; j--){
            if(vec[i] > vec[j]){
                rightNum[i] = max(rightNum[i], rightNum[j]);
            }
        }
        rightNum[i] = rightNum[i] + 1;
    }
    
    //求最长的序列长度
    int maxValue = INT_MIN;
    for(int i = 0; i < N; i++){
        maxValue = max(maxValue, leftNum[i] + rightNum[i] - 1); //
    }
    
    res = N - maxValue;
    
    return;
}

int main(){
    int N = 0;
    cin >> N;
    vector<int> vec;
    int h = 0;
    for(int i = 0; i < N; i++){  
        cin >> h;
        vec.push_back(h);
    }

    int res = 0;
    process(vec, N, res);
    cout << res << endl;
    
    return 0;
}