题解 | 合唱队

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = in.nextInt();
        }
        int[] dp_ins = new int[n];//记录递增最长子序列
        int[] dp_dec = new int[n];//记录递减、、、、
        for (int i = 0; i < n; i++) {
            dp_dec[i] = 1;//默认开始都是1（他自身）
            dp_ins[i] = 1;
        }
        for (int i = 0; i < n; i++) {//动态规划逐渐更新以i为子序列尾巴的递增最长子序列长度
            for (int j = 0; j < i; j++) {
                if (height[i] > height[j]) {
                    dp_ins[i] = Math.max(dp_ins[i], dp_ins[j] + 1);
                }
            }

        }
        for (int i = n - 1; i > 0; i--) {//动态规划逐渐更新以i为子序列头部的递减最长子序列长度
            for (int j = n - 1; j > i; j--) {
                if (height[i] > height[j]) {
                    dp_dec[i] = Math.max(dp_dec[i], dp_dec[j] + 1);
                }
            }
        }
        int max= 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max,dp_dec[i]+dp_ins[i]-1);

        }
        System.out.println(n-max);
    }
}