题解 | #合唱队#

使用两次求最长递增子序列进行解决(从左向右求解一次，从右向左求解一次，最后进行合并)

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] students = new int[n];
        int[] fromLeft = new int[n];
        int[] fromRigt = new int[n];
        for(int i = 0; i < n; i++){
            students[i] = scanner.nextInt();
            fromLeft[i] = 1;
            fromRigt[i] = 1;
        }
        //dp[i]表示以第i个同学为最高同学时需要删除的同学数目
        //则students[0:i]的同学的身高需要呈现出递增,students[i:n]的同学身高需要呈现出递减
        //即左边删除最小数目的学生，右边也删除最小数目的学生
        //其实就是找两次最长递增子序列
        //分别是从左到右找最长递增子序列和从右向左找最长递增子序列
        
        //使用动态规划找
        //使用dp[i]表示以student[i]为末尾的最长递增子序列的长度
        //dp[i] = max(1,dp[j]+1 & student[j]<students[i])
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(students[i] > students[j]){
                    fromLeft[i] = Math.max(fromLeft[i], fromLeft[j] + 1);
                }
            }
        }
        
        for(int i = n - 2; i >= 0; i--){
            for(int j = n - 1; j >i; j--){
                if(students[i] > students[j]){
                    fromRigt[i] = Math.max(fromRigt[i], fromRigt[j] + 1);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            int temp = n-(fromLeft[i] + fromRigt[i] - 1);
            ans = Math.min(ans, temp);
        }
        System.out.println(ans);
    }
    
}