题解 | #合唱队#

import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        int num = in.nextInt();   //总人数
        if(num <=1){
            System.out.println(0); // 不需要出列
        }
        int[] height = new int[num];
        //填充身高数组
        for(int i=0; i<num; i++){
            height[i] = in.nextInt();
        }

        //动态规划：（基础思路）最长递增子序列
        /**
            1. 先找每个位置i的最长递增子序列；
            2. 再找出每个位置i为开始点的最长递减子序列；
            3. 最长合唱队长度=最长递增子序列 + 最长递减子序列 -1
            4. 需要出列的人数就是： 原长度 - 最长合唱队长度         
         */ 

        // 1. 最长递增子序列
        // leftDp[i] 代表的意思： 0-i个元素的最长递增子序列的长度
        // 推导公式： leftDp[i] = max(leftDp[i], leftDp[j] +1)      //leftDp[i]初始化为1，至少有1个元素
        // 说明leftDp[j] （i外层循环，j内层循环从 0 -i遍历，如果出现j<i, height[i]>height[j] , 则出现递增，可以加1）
        int[] leftDp = new int[num];
        //初始化数组，整个数组每个位置的初始值至少为1
        Arrays.fill(leftDp, 1);
        for(int i =1; i<num; i++){
            for(int j =0; j<i; j++){
                //当j<i时，且出现height[j] < height[i],则序列长度+1,相等不算
                if(height[j] < height[i]){
                    leftDp[i] = Math.max(leftDp[i], leftDp[j]+1);     
                }
            }
        }

        // 2. 每个位置i往后的最长递减序列， 即起始位置为数组尾，到i位置是最长递增子序列
        // rightDp[i] 代表的意思是：从数组最后一个，向前遍历到i，最长递增子序列长度
        int[] rightDp = new int[num];
        Arrays.fill(rightDp,1);
        for(int i=num-2; i>=0; i--){
            //当j>i，且出现height[j] > height[i]，则序列长度+1，相等不算
            for(int j=num-1; j>i; j--){
                if(height[j] < height[i]){
                    rightDp[i] = Math.max(rightDp[i], rightDp[j] +1);
                }
            }
        }

        //3. sing[i]: 每个位置下的最长合唱队长度，以i为中心向两边散开，并记录一个最大值
        int[] sing = new int[num];
        int maxLength =0;
        for(int i=0; i<num; i++){
            sing[i] = leftDp[i] + rightDp[i] -1;
            maxLength = Math.max(maxLength, sing[i]);
        }

        //4. 需要出列的人数就是 原始人数num-maxLength
        System.out.println(num - maxLength); 
    }
}