题意整理。

• N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
• 假设K位同学均有对应的身高，合唱队形是指这K位同学的身高先严格递增，再严格递减。

方法一（动态规划）

1.解题思路

这道题本质上是求最长递增子序列，可以通过动态规划来做。只要先把每个位置结尾的最长递增子序列长度计算出来，再逆序遍历数组，求每个位置结尾的最长递增子序列长度（如果是正序，则是该位置开头的最长递减子序列长度），将两者相加再减1即是对应位置的最长合唱队长度。统计所有位置的最长合唱队即可。

• 状态定义：$dp1[i]dp1[i]$表示该位置结尾的最长递增子序列长度，$dp2[i]dp2[i]$表示该位置开头的最长递减子序列长度。
• 状态初始化：初始长度均为1。
• 状态转移：正序遍历时，如果i位置同学身高大于j位置同学，则可以排在j位置同学后面，即$dp1[i]=Math\mathrm{.}max(dp1[i],dp1[j]+1)dp1[i]=Math.max(dp1[i],dp1[j]+1)$。逆序遍历时，如果i位置同学身高大于j位置同学，则j可排在i同学后面，构成递减子序列，即$dp2[i]=Math\mathrm{.}max(dp2[i],dp2[j]+1)dp2[i]=Math.max(dp2[i],dp2[j]+1)$。

2.代码实现

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //同学的总数
            int n=sc.nextInt();
            //N位同学的身高
            int[] arr=new int[n]; 
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            
            //dp1[i]表示该位置结尾的最长递增子序列长度
            int[] dp1=new int[n];
            //给dp1数组赋初值
            Arrays.fill(dp1,1);
            for(int i=0;i<n;i++){
                for(int j=0;j<i;j++){
                    //如果i位置同学身高大于j位置同学，则可以排在j位置同学后面
                    if(arr[j]<arr[i]){
                        dp1[i]=Math.max(dp1[i],dp1[j]+1);
                    }
                }
            }
            
            //dp2[i]表示该位置开头的最长递减子序列长度
            int[] dp2=new int[n];
            //给dp2数组赋初值
            Arrays.fill(dp2,1);
            for(int i=n-1;i>=0;i--){
                for(int j=i+1;j<n;j++){
                    /*如果i位置同学身高大于j位置同学，则可以排在j位置同学后面
                    反过来，则是j可排在i同学后面，构成递减子序列*/
                    if(arr[j]<arr[i]){
                        dp2[i]=Math.max(dp2[i],dp2[j]+1);
                    }
                }
            }
            
            //统计每个位置的合唱队形长度最大值
            int max=0;
            for(int i=0;i<n;i++){
                max=Math.max(max,dp1[i]+dp2[i]-1);
            }
            
            System.out.println(n-max);
        }
    }
}

3.复杂度分析

• 时间复杂度：状态转移过程中，两层循环总共执行$n\ast (n-1)\mathrm{/}2n*(n-1)/2$次，所以时间复杂度为$O(n^2)O(n^2)$。
• 空间复杂度：需要额外大小为n的dp1数组和dp2数组，所以空间复杂度为$O(n)O(n)$。

方法二（二分优化）

1.解题思路

• 新建dp1数组和dp2数组，$dp1[i]dp1[i]$表示该位置结尾的最长递增子序列长度，$dp2[i]dp2[i]$表示该位置开头的最长递减子序列长度。
• 然后维护一个递增数组tail1，如果tail1数组为空，或arr[i]大于tail1数组末尾元素，直接将arr[i]放在tail1数组末尾，tail1数组的长度即是当前位置结尾的最长递增子序列长度。否则，二分法找到arr[i]在tail1数组中的位置，假设该位置为l，则l+1为当前位置结尾的最长递增子序列长度。
• 对于dp2数组，逆序遍历arr数组，维护一个递增数组tail2，如果tail2数组为空，或arr[i]大于tail2数组末尾元素，直接将arr[i]放在tail2数组末尾，tail2数组的长度即是当前位置开头的最长递减子序列长度。否则，二分法找到arr[i]在tail2数组中的位置，假设该位置为l，则l+1为当前位置开头的最长递减子序列长度。
• 最后，遍历dp1、dp2数组，统计每个位置的合唱队形长度最大值。

动图展示（只考虑dp1数组）：

2.代码实现

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //同学的总数
            int n=sc.nextInt();
            //N位同学的身高
            int[] arr=new int[n]; 
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            
            //dp1[i]表示该位置结尾的最长递增子序列长度
            int[] dp1=new int[n];
            //tail1表示维护的一个严格递增子序列
            int[] tail1=new int[n];
            //tail1数组的最后一个元素下标
            int end1=-1;
            for(int i=0;i<n;i++){
                //如果tail1数组为空，或arr[i]大于tail1数组末尾元素，直接将arr[i]放在tail1数组末尾
                if(i==0||tail1[end1]<arr[i]){
                    tail1[++end1]=arr[i];
                    dp1[i]=end1+1;
                }
                //否则，二分法找到arr[i]在tail1数组中的位置
                else{
                    int l=0;
                    int r=end1;
                    while(l<r){
                        int mid=l+(r-l)/2;
                        if(tail1[mid]>=arr[i]){
                            r=mid;
                        }
                        else{
                            l=mid+1;
                        }
                    }
                    tail1[l]=arr[i];
                    dp1[i]=l+1;
                }
                
            }
            
            //dp2[i]表示该位置开头的最长递减子序列长度
            int[] dp2=new int[n];
            //tail2表示维护的一个严格递增子序列
            int[] tail2=new int[n];
            //tail2数组的最后一个元素下标
            int end2=-1;
            for(int i=n-1;i>=0;i--){
                //如果tail2数组为空，或arr[i]大于tail2数组末尾元素，直接将arr[i]放在tail2数组末尾
                if(i==n-1||tail2[end2]<arr[i]){
                    tail2[++end2]=arr[i];
                    dp2[i]=end2+1;
                }
                //否则，二分法找到arr[i]在tail2数组中的位置
                else{
                    int l=0;
                    int r=end2;
                    while(l<r){
                        int mid=l+(r-l)/2;
                        if(tail2[mid]>=arr[i]){
                            r=mid;
                        }
                        else{
                            l=mid+1;
                        }
                    }
                    tail2[l]=arr[i];
                    dp2[i]=l+1;
                }
                
            }
            
            //统计每个位置的合唱队形长度最大值
            int max=0;
            for(int i=0;i<n;i++){
                max=Math.max(max,dp1[i]+dp2[i]-1);
            }
            
            System.out.println(n-max);
        }
    }
}

3.复杂度分析

• 时间复杂度：总共有两层循环，内层循环为二分查找方式，时间复杂度为$O(lo{g}_{2}n)O(log\_2n)$，所以时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$。
• 空间复杂度：需要额外大小为n的dp1、dp2数组和tail1、tail2数组，所以空间复杂度为$O(n)O(n)$。