题解 | #合唱队# 使用动态规划处理最多下降子序列

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
    let dataArr = [];
    let N = 0;
    while ((line = await readline())) {
        // 请最少的同学（N-K）出列， 剩下的人排成合唱队
        // 存在一位同学， 左侧递增，右侧递减（K最大）
        dataArr.push(line);
        const len = dataArr.length;
        // 处理多行输入
        if (len == 1) {
            N = Number(dataArr[0]);
        } else {
            // 需要把输入的字符串转成数字
            resultArr = dataArr[1].split(" ").map(item => Number(item));
            // dp1 dp2表示左右两侧的动态规划
            // 1.左右两侧的下降子序列
            // 2.找到中心点
            const n = resultArr.length;
            const dp1 = new Array(n).fill(0);
            const dp2 = new Array(n).fill(0);

            // 左侧下降子序列
            for (let i = 0; i < n; i++) {
                // dp1 => 左侧符合条件的个数 （递增）
                dp1[i] = 1;
                for (let j = 0; j < i; j++) {
                    if (resultArr[i] > resultArr[j]) {
                        dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                    }
                }
            }

            for (let i = n - 1; i >= 0; i--) {
                // dp2 => 右侧符合条件的个数 （递减）
                dp2[i] = 1;
                for (let j = n - 1; j > i; j--) {
                    if (resultArr[i] > resultArr[j]) {
                        dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                    }
                }
            }

            let max = 0
            for (let i = 0; i < n; i++) {
                // 找核心点
                if (max <= dp1[i] + dp2[i] - 1) {
                    max = dp1[i] + dp2[i] - 1
                }
            }
            console.log(N - max)
        }
    }
})();