题解 | 合唱队

import java.util.Scanner;
import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = scanner.nextInt();
        }
        // 1. 计算从左到右的 LIS（最长递增子序列）
        int[] lis = new int[n];
        Arrays.fill(lis, 1); // 每个位置至少长度为1
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (heights[j] < heights[i]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        // 2. 计算从右到左的 LDS（最长递减子序列）
        int[] lds = new int[n];
        Arrays.fill(lds, 1); // 每个位置至少长度为1
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (heights[j] < heights[i]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        // 3. 计算合唱队形的最长长度
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, lis[i] + lds[i] - 1);
        }

        // 4. 最少需要删除的人数
        int minRemove = n - maxLen;
        System.out.println(minRemove);
    }
}