题解 | #合唱队#

const rl = require("readline").createInterface({ input: process.stdin })
let arr = []
rl.on('line', function(line) {
    arr.push(line)
})
rl.on('close', function() {
    // console.log(arr)
    let tempArr = arr[1].split(' ')
    // console.log(tempArr)
    let left = new Array(tempArr.length).fill(1)
    for(let i=1;i<tempArr.length;i++) {
        for(let j=0;j<i;j++) {
            if(parseInt(tempArr[i])>parseInt(tempArr[j])) {
                left[i] = Math.max(left[i], left[j]+1)
            }
        }
    }
    // console.log(left)

    let right = new Array(tempArr.length).fill(1)
    for(let i=tempArr.length-2;i>=0;i--) {
        for(let j=tempArr.length-1;j>i;j--) {
            if(parseInt(tempArr[i])>parseInt(tempArr[j])) {
                right[i] = Math.max(right[i], right[j]+1)
            }
        }
    }
    // console.log(right)
    let maxLenth = 0
    for(let i=0;i<tempArr.length;i++) {
        maxLenth = Math.max(maxLenth, left[i]+right[i]-1)
    }
    // console.log(maxLenth)
    console.log(tempArr.length-maxLenth)


})

此题类似走梅花桩，都是通过动态规划找出每个同学的最长递增和最长递减子序列，然后对比两个子序列的大小，找出最长的合唱队队形，通过用总数-最长合唱队队形得出来需要最少出列人数