题解 | #合唱队#

动态规划算法：

1. 增序列算一遍得出dp_zeng[];
2. 减序列算一遍得出dp_jian[];
3. 最长的合唱队形为 Max(dp_zeng[i]+dp_jian[i]-1), 则需要出列的为 总数-Max

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

void async function () {
    // Write your code here
    let arr = [];
    while(line = await readline()){
        arr.push(line);
    }
    let count = parseInt(arr[0]);
    let nums = arr[1].split(' ');
    if(nums[count -1] == ''){
        nums.splice(count-1,1);
    }
    nums = nums.map((item)=>{return parseInt(item)});
    let dp_zeng = new Array(count).fill(1), dp_jian = new Array(count).fill(1);
    for(let i=1;i<count;i++){ // 算增序列
        let max_zeng = 0;
        for(let k=0;k<i;k++){   
            if(nums[k]<nums[i]){
                max_zeng = Math.max(max_zeng,dp_zeng[k]+1);
            }
        }
        dp_zeng[i] = Math.max(max_zeng,dp_zeng[i]);
    }
    for(let j=count-2;j>-1;j--){ // 算减序列
        let max_jian = 0;
        for(let k=count-1;k>j;k--){
            if(nums[k]<nums[j]){
                max_jian = Math.max(max_jian,dp_jian[k]+1);
            }
        }
        dp_jian[j] = Math.max(max_jian,dp_jian[j]);
    }

    let big_xulie_len = 0
    for(let k=0;k<count;k++){
        let tmp = dp_zeng[k] + dp_jian[k] - 1;
        big_xulie_len = Math.max(big_xulie_len,tmp);
    }
    let remove_num = count - big_xulie_len;
    console.log(remove_num);
}()