题解 | 合唱队

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int res=n; //代表最少出列的同学数
        /**
        以a[i]为最高的同学，a[0,i]且以a[i]结尾的最长递增子序列长度l,  a[i,n-1]且以a[i]开头的最长递减子序列长度r,   需要出列的n-l-r;
        
         */
        in.nextLine();
        int[] nums=new int[n];//存储n个数
        int[] x=new int[n];//x[i]代表l
        int[] y=new int[n];//y[i]代表r
        for(int i=0;i<n;i++){
            x[i]=1;
            y[i]=1;
        }

        for(int i=0;i<n;i++){
            nums[i]=in.nextInt();
        }
        for(int i=1;i<n;i++){//从第二个位置开始计算
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                  x[i]=Math.max(x[i],x[j]+1);
                }
            }
        }

        for(int i=n-2;i>=0;i--){//从倒数第二个位置开始计算
            for(int j=i;j<n;j++){
                if(nums[i]>nums[j]){
                  y[i]=Math.max(y[i],y[j]+1);
                }
            }
        }

        for(int i=0;i<n;i++){
            res=Math.min(res, n-(x[i]+y[i])+1);
        }
        System.out.println(res);

    }
}

关键在于把问题拆分为两个子序列