题解 | #合唱队#

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
// 同学总数
let total = 0
// 身高数组
const heights = []

rl.on('line', function (line: string) {
    if (total === 0) {
        total = parseInt(line, 10)
    } else {
        line.split(' ').forEach((height) => {
            heights.push(parseInt(height, 10))
        })
    }
});

// 找出最长上升子序列的长度
const findMax = (nums: number[]) => {
    const dp = Array.from({length: nums.length}, () => 1)
    const tails = Array.from({length: nums.length})
    let len = 0
    for (let i=0; i<nums.length; i+=1) {
        let k=0
        let j=len
        while (k<j) {
            const index = Math.floor((k+j)/2)
            if (tails[index] < nums[i]) {
                k = index + 1
            } else {
                j = index
            }
        }
        tails[k] = nums[i]
        if (k === len) {
            len += 1
        }
        dp[i] = len
    }
    return dp
}

rl.on('close', () => {
    let min = Infinity
    // 找出每种合唱队形，并计算所需同学出列的数量，最后取最小的数量
    const leftDP = findMax(heights)
    const rightDP = findMax(heights.reverse())
    for(let i=0; i<total; i+=1) {
        min = Math.min(
            min,
            total - (leftDP[i] + rightDP[total - i - 1] - 1)
        )
    }
    console.log(min)
})