题解 | 合唱队

import java.util.Scanner;
public class  Main{
    public static void main(String[] args){
        Scanner sc  = new Scanner(System.in);
        int n = sc.nextInt();
        int h[] = new int[n];
        for(int i = 0;i<n;i++){
            h[i] = sc.nextInt();
        }

        int dpl[] = new int[n];
        int dpr[] = new int[n];
        for(int i = 0;i<n;i++){
            dpl[i] = 1;
            dpr[i] = 1;
        }

        for(int i = 0;i<n;i++){
            for(int j = 0;j<i;j++){
                if(h[j]<h[i]){
                    dpl[i] = Math.max(dpl[i],dpl[j]+1);
                }
            }
        }

        for(int i = n-1;i>=0;i--){
            for(int j = n-1;j>i;j--){
                if(h[j]<h[i]){
                    dpr[i] = Math.max(dpr[i] ,dpr[j]+1);
                }
            }
        }

        int maxlength  = 0;
        for(int i = 0;i<n;i++){
            maxlength  = Math.max(maxlength,dpl[i]+dpr[i]-1);
        }
        System.out.println(n-maxlength);
    }
}