算法思路

这道题目要求我们通过最少的出列人数，使得剩余的同学身高满足合唱队形的要求。核心思路是使用 动态规划 来求解问题。

  1. 问题拆解：
    • 合唱队形分为两部分：一个严格递增的子序列，后接一个严格递减的子序列。
    • 我们需要找到每个同学在「从左到右」的最长递增子序列长度和「从右到左」的最长递增子序列长度。
  2. 动态规划：
    • 使用两个数组 dp_inc 和 dp_dec 分别存储从左到右和从右到左的最长递增子序列长度。
    • 对于每个同学，其在合唱队形中能够构成的最大长度为 dp_inc[i] + dp_dec[i] - 1。
  3. 结果计算：
    • 找到所有 dp_inc[i] + dp_dec[i] - 1 的最大值，表示该情况下能够保留的最多人数。
    • 最少需要出列的人数为总人数减去这个最大值。

算法核心

我们通过动态规划计算每个同学的：

  1. 左侧递增子序列的长度 (dp_inc[i])： 这个值表示从第 1 名同学到第 i 名同学中，包含第 i 名同学的最长递增子序列的长度。
  2. 右侧递减子序列的长度 (dp_dec[i])： 这个值表示从第 i 名同学到第 N 名同学中，包含第 i 名同学的最长递减子序列的长度。

对于每个同学 i，如果把 i 设为合唱队形的「最高点」，那么：

  • 整体合唱队形的长度为：
    （减 1 是因为 i 的身高被两次计算了）。

Code

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 输入处理
    const N = parseInt(await readline()); // 同学总数
    const heights = (await readline()).split(" ").map(Number); // 同学身高

    // 初始化动态规划数组
    const dp_inc = Array(N).fill(1); // 从左到右的递增子序列
    const dp_dec = Array(N).fill(1); // 从右到左的递增子序列

    // 计算从左到右的最长递增子序列长度
    for (let i = 1; i < N; i++) {
        for (let j = 0; j < i; j++) {
            if (heights[i] > heights[j]) {
                dp_inc[i] = Math.max(dp_inc[i], dp_inc[j] + 1);
            }
        }
    }

    // 计算从右到左的最长递增子序列长度
    for (let i = N - 2; i >= 0; i--) {
        for (let j = N - 1; j > i; j--) {
            if (heights[i] > heights[j]) {
                dp_dec[i] = Math.max(dp_dec[i], dp_dec[j] + 1);
            }
        }
    }

    // 找到最长合唱队形的人数
    let max_chorus = 0;
    for (let i = 0; i < N; i++) {
        max_chorus = Math.max(max_chorus, dp_inc[i] + dp_dec[i] - 1);
    }

    // 计算最少需要出列的人数
    const result = N - max_chorus;

    console.log(result);
}();

复杂度分析

  1. 时间复杂度：
    • 两个动态规划过程：分别需要两层循环遍历，时间复杂度为 O(N^2^)。
    • 总时间复杂度：O(N^2^)。
  2. 空间复杂度：
    • 需要额外的两个数组 dp_inc 和 dp_dec 来存储递增序列长度，空间复杂度为 O(N)。
    • 总空间复杂度：O(N)。