题解 | #合唱队#

#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        vector<int> list;
        int left[n],right[n];
        for(int i=0;i<n;i++){
            int num;cin>>num;
            list.push_back(num);
            left[i] = right[i] = 1;
        }
        
        int res[n];
        for(int i=0;i<list.size();i++){
            //计算左侧的LCS,当前面的
            // int max_ = 0;
            for(int j=0; j<i; j++){
                if(list[j] < list[i]){
                    left[i] = max(left[i],left[j]+1);
                }
            }
        
        }
        for(int i=list.size()-1;i>=0;i--){
            for(int j=i+1; j<list.size(); j++){
                if(list[j] < list[i] ){
                    right[i] = max(right[i],right[j]+1);
                    // min_ = list[j];
                }
            }   
        }
        for(int i=0;i<list.size();i++){
            // cout<<"left "<<left[i]<<" right: "<<right[i];
            res[i] = left[i]+right[i]-1;
        }
        int find_max = 0;
        for(int i=0;i<list.size();i++){
            if(res[i] >find_max )
                find_max = res[i];
        }

        cout<<n-find_max<<endl;;
    }
}

for(int i=0;i<list.size();i++){
            for(int j=i+1;j<list.size();j++)
            {
                if(list[j]<list[i])
                    right2[i] = max(right2[i],right2[j]+1);
            }
        }