题解 | #合唱队#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(function(arr));
        }
    }
    private static int function(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int[] forward = forward(arr);
        int[] backward = backward(arr);
        int max = 0;
        for (int i = 0; i < n; i++) {
            int sum = forward[i] + backward[i];
            max = sum > max ? sum : max;
        }
        return n - (max - 1);
    }


    private static int[] forward(int[] arr) {
        int n = arr.length;
        int[] forward = new int[n];
        for (int i = 0; i < n; i++) {
            forward[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && forward[j] + 1 > forward[i]) {
                    forward[i] = forward[j] + 1;
                }
            }
        }
        return forward;
    }

    private static int[] backward(int[] arr) {
        int n = arr.length;
        int[] backward = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            backward[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (arr[j] < arr[i] && backward[j] + 1 > backward[i]) {
                    backward[i] = backward[j] + 1;
                }
            }
        }
        return backward;
    }
}

解题思路:

1, 对每一个位置, 找到从左往右满足身高升序队列的最大可能人数;

2, 对每一个位置, 找到从右往左满足身高升序队列的最大可能人数;

3, 结合上述思路, 可以知道在每一个位置, 满足两边身高降序排列的最大可能人数;

4, 总人数和上一步求解到的最大数的差值, 就是我们需要的最小出列人数