题解 | 合唱队

import java.util.Scanner;

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();
        }

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

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

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (left[i] >= 2 && right[i] >= 2) {
                int current = left[i] + right[i] - 1;
                if (current > maxLen) {
                    maxLen = current;
                }
            }
        }

        if (maxLen >= 3) {
            System.out.println(n - maxLen);
        } else {
            System.out.println(n);
        }
    }
}

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

思路：

1. 输入处理：读取同学数量n和每位同学的身高数组h。
2. 计算最长递增子序列：使用动态规划从左到右遍历，计算每个位置左边的最长严格递增子序列长度，存储在left数组中。
3. 计算最长递减子序列：使用动态规划从右到左遍历，计算每个位置右边的最长严格递减子序列长度，存储在right数组中。
4. 寻找最大合唱队形长度：遍历每个位置，若其左右两边均存在至少一个同学，则计算当前可能的合唱队形长度，并更新最大值。
5. 输出结果：若存在有效的合唱队形，输出需要出列的最少人数；否则输出总人数，表示无法形成有效队形，所有同学均需出列。