题解 | 合唱队

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int[] height = new int[num];
        int[] left = new int[num];  //以i结尾的最长递增子序列
        Arrays.fill(left, 1);
        int[] right = new int[num];  //以i开头的最长递减子序列
        Arrays.fill(right, 1);
        for (int i = 0; i < num; i++) {
            height[i] = in.nextInt();
        }

        //找以i结尾最长递增子序列长度
        for(int i = 1; i < num; i++) {  //以i结尾
            for (int j = 0; j < i; j++) {  //以j开头i结尾的递增子序列
                if (height[i] > height[j]) {
                    left[i] = Math.max(left[i], left[j]+ 1);
                }
            }
        }
        //以i开头最长递减子序列长度
        for(int i = num - 2; i >= 0; i--) {  //从结尾开始，找以i结尾的递增
            for (int j = num - 1; j > i; j--) {
                if (height[i] > height[j]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }

        int index = 1;  //记录i
        int length = left[0] + right[0];
        for (int i = 1; i < num; i++) {
            length = Math.max(length, left[i] + right[i]);
        }
        System.out.print((num - length +1) >= 0 ? (num - length +1) : 0);
    }
}