题解 | #合唱队#

对热评解法添加的自己关于动态规划做此题的理解。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (sc.hasNextInt()) { // 注意 while 处理多个 case
            int n=sc.nextInt();
            //处理输入
            int [] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }

            solve(n,arr);
        }
    }
    public static void  solve(int n,int[] arr){
        int [] leftlen=new int[n];//存储每个数左边最长递增序列
        int [] rightlen=new int[n];//存储每个数右边最长递减序列
        leftlen[0]=1;
        rightlen[n-1]=1;
        //计算每个位置左侧的最长递增
        for(int i=0;i<n;i++){
            leftlen[i]=1;//先假设第i个人左边没有递增序列，就他自己
            for(int j=0;j<i;j++){
                //因为要对第i个人和他左边的所有人进行比较，所以j<i
                if(arr[i]>arr[j]){
                    /** 因为满足条件第i个人比第j个人高
                    所以此时开始寻找第i个人左边的每个人的左边最大递增序列的长度加上这个人
                    后的最大值就是第i个人左边最大递增序列的长度
                    leftlen相当于暂存空间，存储最大值的，遇到更大的就更新一下
                    */
                    leftlen[i]=Math.max(leftlen[j]+1,leftlen[i]);
                }
            }
        }
        
        //计算每个位置右侧的最长递减
        for(int i=n-1;i>=0;i--){//从右往左找
            rightlen[i]=1;//假设第i个人右边没有递减序列，就他自己
            for(int j=n-1;j>i;j--){//对第i个人和他右边的所有人比较，所以j>i
                if(arr[j]<arr[i]){//第i个人要比右边的人高才能递减
                    rightlen[i]=Math.max(rightlen[j]+1,rightlen[i]);
                }
            }
        }
        //  计算以每个人为中心，符合合唱队规则的队列长度
        int [] result=new int[n];
        for(int i=0;i<n;i++){
            result[i]=leftlen[i]+rightlen[i]-1;//因为第i个人算了两次，要减去1
        }

        int max=1;
        for(int i=0;i<n;i++){
            max=Math.max(result[i],max);
        }
        System.out.println(n-max);//输出剔除的人的最少个数
    }
}