题解 | #合唱队#

获取递增的最大序列

获取递减的最大序列

反转相加得到新的序列即为左边递增，右边递减的最大序列

本题第一次算迷惑的地方为先找到最大身高的同学，进入误区，因为最大身高不一定要参加合唱队，参加的可能是比他低的两位同学。

let line ;

let arr = []

while(line = readline()){
    arr.push(line)
    if(arr.length == 2){
        let stud = parseInt(arr[0])
        let hight = arr[1].split(' ').map(i=>parseInt(i));
        let max = 0
        let dp = []
        for(let i = 0;i<hight.length;i++){
            dp[i] = 1
            for(let j = 0;j<i;j++){
                if(hight[i]>hight[j]){
                    dp[i] = Math.max(dp[j] + 1,dp[i])
                }
            }
        }
        let dp1 = []
        let newArr = hight.reverse()
        for(let i = 0;i<newArr.length;i++){
            dp1[i] = 1
            for(let j = 0;j<i;j++){
                if(newArr[i]>newArr[j]){
                    dp1[i] = Math.max(dp1[j] + 1,dp1[i])
                }
            }
        }
        let temp = []
        for(let i = 0;i<dp.length;i++){
            temp.push(dp[i] + dp1[dp.length - i - 1])
        }
        for(let i of temp){
            if(i>max){
                max = i
            }
        }
        console.log(stud- (max - 1));
        arr = []
    }
}