题解 | #合唱队#

import java.util.Scanner;
import java.util.Arrays;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        Integer nums = Integer.valueOf(sc.nextLine());
        String input = sc.nextLine();
        String[] arr = input.split(" ");
        int[] src = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();
        // 找到每个元素 作为中间元素  左边的数量    然后右边的数量   位置不变嘛    移除最少  意思就是 长度最大

        int result=0;  // 以dp[i] 为底部的  左右的最大长度

        int[] left =new int[src.length];

        for (int i = 0; i < src.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (src[j]<src[i]){
                    // 数学归纳法是关键
                    left[i]=Math.max(left[i],left[j]+1);
                }
            }
        }

        int[] right =new int[src.length];
        for (int i = src.length-1; i >0 ; i--) {
            for (int j = src.length-1; j >= i; j--) {
                if (src[j]<src[i]){
                    // 这里面逻辑还是有问题
                    right[i]=Math.max(right[i],right[j]+1);
                }
            }
        }

        for (int i = 0; i < left.length; i++) {
            result=Math.max(left[i]+right[i]+1,result);
        }

        System.out.println(nums-result);
    }
}