题解 | #合唱队# #最长递增子队列#

思路

这里思路参考了一部分https://blog.nowcoder.net/n/3b8f1d7bd4c3457ebd86558b73a5a673?f=comment

因为无法一步知道一个人的左右最长队列，所以先尽可能的考虑到每个人都可能作为中间最高那个人，然后找该人两边的左递增右递队员身高数列。

这里主要是找到每个人的最长左递增右递减队员长度。所以不妨拆开每个人来分析，最后汇总判断。寻找最长队员长度的时候，有点类似于贪心，比如找右边较高者，若存在一位，则把左边的递增队员纳入他的子列，同时判断哪个子队员最长，找出最长的之队员即可。

其实这个题如何判断最长递增数列这种解题思想值得掌握。这个可以变形很多题。

Java代码

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int a = in.nextInt();//数据行数
            int[] line=new int[a];//用数组接收
            //left[i]表示包含从左到右递增的最长的队员个数
            //比如用例186 186 150 200 160 130 197 200
            //left={1 1 1 2 2 1 3 4}，left[6]=3,表示最长递增队员数3，包含本人
            int[] left=new int[a];
            //right同理
            int[] right=new int[a];
            //初始赋值
            for(int i=0;i<a;i++){
                line[i]=in.nextInt();
                left[i]=1;//初始为1表示只有本人
                right[i]=1;               
            }
            int lefttemp=0; //          
            for(int i=1;i<a;i++){
                lefttemp=i;
                for(int j=i-1;j>=0;j--){
                    if(line[j]<line[lefttemp]){
                        if((left[i])<left[j]+1){
                            //若存在比当前队员身高低的，则判断他的最长递增数，
                            //+1表示加上当前队员后的人数
                            //若前面队员本身队员数+1后能大于当前队员数，则引入新的 队列
                            left[i]=left[j]+1;
                        }
                    } 
                }
            }
            for(int i=a-2;i>=0;i--){
                int righttemp=i;
                for(int j=i+1;j<a;j++){
                    if(line[j]<line[righttemp]){
                        if((right[i])<right[j]+1){
                            //类似前面的。
                            right[i]=right[j]+1;
                        }
                    } 
                }
            }
            int max=left[0]+right[0]-1;
            for(int i=0;i<a;i++){
                //找出包含本人的左右最长大的队员数
                //因为本人重复计了一次，则需要减1；
                if(max<left[i]+right[i]-1){
                    max=left[i]+right[i]-1;
                }
            }
            System.out.println(a-max);
        }
    }    
}