题解 | 合唱队形

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = in.nextInt();
        }

        int[] left = new int[n];
        Arrays.fill(left, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (heights[j] < heights[i]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }

        int[] right = new int[n];
        Arrays.fill(right, 1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (heights[j] < heights[i]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, left[i] + right[i] - 1);
        }

        System.out.println(n - maxLen);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取同学的总数和每个同学的身高。
2. 计算左边最长递增子序列：使用动态规划计算每个同学左边的最长递增子序列的长度。
3. 计算右边最长递减子序列：同样使用动态规划，从右向左计算每个同学右边的最长递减子序列的长度。
4. 合并结果：遍历每个同学，计算以该同学为中间点的合唱队形长度，并找到最大值。最终输出需要出列的同学数目，即总人数减去最长合唱队形长度。