题解 | #合唱队#

动态规划

思路见代码注释

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());
        String[] split = br.readLine().split(" ");
        int[] nums = Arrays.stream(split).mapToInt(Integer::parseInt).toArray();

        int[] left = new int[n], right = new int[n];
        // 先找到每个位置 i 左侧的最长上升子序列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }

        // 再找到每个位置 i 右边的最长下降子序列
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[j] < nums[i]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }

        // 如果以位置 i 为中心，可以构成的合唱队的最大长度为：
        // 左侧最长上升子序列长度 + 右侧最长下降子序列长度 + 1
        // 加 1 是因为位置 i 没有被计算
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, left[i] + right[i] + 1);
        }
        // 所以最少需要出列的人数为：总人数 - 合唱队的最大长度
        pw.println(n - maxLen);

        pw.flush();
        pw.close();
        br.close();
    }
}