题解 | 合唱队形

import java.util.Scanner;

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

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

        int[] dp = new int[n];
        for (int j = n - 1; j >= 0; j--) {
            dp[j] = 1;
            for (int k = j + 1; k < n; k++) {
                if (t[k] < t[j]) {
                    dp[j] = Math.max(dp[j], dp[k] + 1);
                }
            }
        }

        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                if (t[j] < t[i] && dp[j] > max) {
                    max = dp[j];
                }
            }
            right[i] = max;
        }

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

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

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

思路：

1. 输入处理：读取同学总数和他们的身高数据。
2. 计算 left 数组：left[i] 表示以第 i 个同学结尾的最长递增子序列的长度。
3. 计算 dp 数组：dp[j] 表示从第 j 个同学开始的最长递减子序列的长度。
4. 计算 right 数组：right[i] 表示第 i 个同学右边所有比它矮的同学的最长递减子序列的最大长度。
5. 合并结果：遍历每个位置，计算 left[i] + right[i] 的最大值，从而得到最长合唱队形的长度，最终输出需要出列的同学数。