题解 | #合唱队#

import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * 8
 * 186 186 150 200 160 130 197 200
 * 4
 * 说明：
 * 由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        /**
         实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。
         输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
         */
        while (in.hasNextLine()) {
            String nextLine = in.nextLine();
            if (Objects.isNull(nextLine) || nextLine.equals("")) {
                break;
            }
            int n = Integer.parseInt(nextLine);
            String line = in.nextLine();
            List<Integer> student = Arrays.stream(line.split(" "))
                                    .map(Integer::parseInt)
                                    .collect(Collectors.toList());
            int max = 0;
            int[] leftDp = leftDp(student);
            int[] rightDp = rightDp(student);
            // 遍历每一个学生，找出当前的dp最优值
            for (int i = 0; i < n; i++) {
                max = Math.max(leftDp[i] + rightDp[i], max);
            }
            // 需额外减去最高中间那个人
            System.out.println(student.size() - (max + 1));
        }
    }

    // 遍历左侧每个位置的最大值，包含中间值
    public static int[] leftDp(List<Integer> student) {
        int size = student.size();
        int[] dp = new int[size];
        for (int i = 0; i < size; i++) {
            // dp是记录当前位置的递增人数
            dp[i] = 0;
            // 假定current是最高的那位学生
            Integer current = student.get(i);
            // 遍历计算出长度
            for (int j = 0; j < i; j++) {
                Integer iterator = student.get(j);
                int iteratorBest = dp[j];
                // 只要当前身高比最高身高高，那么就认为可以把之前认为最高的那个序列作为递增序列的一部分，作为当前身高的递增人数值
                if (iterator < current) {
                    // 取出不同递归队伍中的最大值作为当前学生的最多人数值
                    dp[i] = Math.max(iteratorBest + 1, dp[i]);
                }
                // 如果身高相等则不做处理
                // 如果身高高于当前学生也不做处理
            }
        }
        return dp;
    }

    // 逆向遍历右侧递归的最大值
    public static int[] rightDp(List<Integer> student) {
        int size = student.size();
        int[] dp = new int[size];
        for (int i = size - 1; i >= 0; i--) {
            dp[size - 1] = 0;
            // 假定current是最高的那位学生
            Integer current = student.get(i);
            // 遍历计算出长度
            for (int j = size - 1; j > i; j--) {
                Integer iterator = student.get(j);
                int iteratorBest = dp[j];
                // 只要当前身高比最高身高高，那么就认为可以把之前认为最高的那个序列作为递增序列的一部分，作为当前身高的递增人数值
                if (student.get(j) < current) {
                    dp[i] = Math.max(iteratorBest + 1, dp[i]);
                }
            }
        }
        return dp;
    }
}