题解 | 合唱队

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) h[i] = in.nextInt();

        //pre[i]记录以i为结尾的严格递增子序列的长度
        int[] pre = new int[n];
        //aft[i]记录以i为开始的严格递减子序列的长度
        int[] aft = new int[n];
        pre[0] = 1;
        aft[n - 1] = 1;
        //维护pre
        for (int i = 1; i < n; i++) {
            pre[i] = 1;
            for (int j = 0; j < i; j++) {
                if (h[i] > h[j])pre[i] = Math.max(pre[i], pre[j] + 1);
            }
        }

        //维护aft
        for (int i = n - 2; i >= 0; i--) {
            aft[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (h[j] < h[i]) aft[i] = Math.max(aft[i], aft[j] + 1);
            }
        }

        int res = n;
        //
        for (int i = 0; i < n; i++) {
            int preLen = pre[i] - 1;
            int aftLen = aft[i] - 1;
            if (preLen >= 1 && aftLen >= 1)
                res = Math.min(res, (i - preLen) + (n - i - 1 - aftLen));
        }
        System.out.println(res);
    }
}