题解 | #合唱队#

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());
            // dp表示当前状态队伍中,当前人为最高点时，队伍的最多递增人数
            // 左边人数
            int[] dpLeft = new int[student.size()];
            // 右边的人数
            int[] dpRight = new int[student.size()];
            // 初始化
            // 当队伍里面只有1个人时，最终队伍人数就是1
            dpLeft[0] = 1;
            dpRight[student.size() - 1] = 1;
            // 初始最终只有1个人
            int result = 1;
            // 左队伍人数逐渐增加，刷新状态
            for (int i = 0; i < student.size(); i++) {
                // 先默认自成一派
                dpLeft[i] = 1;
                // 当前人的高度
                Integer current = student.get(i);
                // 如果当前的人比前一个遍历还高或者跟它一样高
                // 如果当前的人比前一个遍历还矮，则它的dpLeft值应当是dpLeft中比前一个状态稍微矮一个级的+1
                for (int j = 0; j < i; j++) {
                    if (student.get(j) < current) {
                        dpLeft[i] = Math.max(dpLeft[i], dpLeft[j] + 1);
                    }
                }

            }

            // 右队伍人数逐渐增加，刷新状态
            for (int i = student.size() - 1; i >= 0; i--) {
                // 先默认自成一派
                dpRight[i] = 1;
                // 当前人的高度
                Integer current = student.get(i);
                // 如果当前的人比前一个遍历还高或者跟它一样高
                // 如果当前的人比前一个遍历还矮，则它的dpLeft值应当是dpLeft中比前一个状态稍微高一个级的+1
                for (int j = student.size() - 1; j > i; j--) {
                    if (student.get(j) < current) {
                        dpRight[i] = Math.max(dpRight[i], dpRight[j] + 1);
                    }
                }
            }
            // 左队伍+右队伍，遍历出最大值
            for (int i = 0; i < student.size() - 1; i++) {
                result = Math.max(dpLeft[i] + dpRight[i], result);
            }
            // 需要减去中间那个重复的人，合唱队队伍人数最多
            System.out.println(student.size() - result+1);
        }
    }
}