合唱队js题解

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设K位同学从左到右依次编号为 1，2…，K ，他们的身高分别为T1​,T2​,…,TK​ ，若存在i(1≤i≤K) 使得T1​Ti+1​>......>TK​，则称这K名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

例子：

123 124 125 123 121 是一个合唱队形

123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求

123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

数据范围： 1≤n≤3000

输入描述：
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输出描述：
最少需要几位同学出列

示例1
输入：

8
186 186 150 200 160 130 197 200
输出：

4
说明：

由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130

•  本题是一维数组的动态规划题目，一个位置上的左右的最长递增子序列可以由上一个位置的推出，因此符合动态规划的思想。
• 我们需要用dp【i】来表示一个位置上的左边的最长递增子序列的长度，那么从左往右的递增序列，假设dp[i]，i=3,以索引3位置上的同学为中间，他的左边的递增序列为186 200或者150 200 ，长度为2。索引0、1、2位置上的数都可以作为这个dp[3]的序列中的一员，因此可以得到递推公式：dp[i] = Math.max(dp[i],dp[j]+1),其中j是用来遍历i索引之前的每个位置，通过得到每个位置上的dp[j]的最大值，来得到dp[i]位置上的最大值。
• 中间值右边的序列是从左往右递减的，我们不妨换个思路，将这个数组反转，那么求原数组中从左往右递减的序列，就是求反转后的数组从左往右递增的序列。恰好跟上面dp[i]求解思路是相同的。因此可以将动态规划转移方程封装成一个函数，将反转后的数组传入函数中，在得到dp数组结果后在反转回来。
• 计算这个合唱序列人数时，是通过中间人i左边序列加上右边序列得到的，i进行了两次计算，因此需要减去一个i。
• 最终通过总人数n减去dp1[i]+dp2[i] -1得到的就是要出列的人数。

var num;
while(num = parseInt(readline())){
    const arr = readline().split(' ').slice(0,num).map(n => parseInt(n));
    let dp1 = MaxList(arr);
    //求从右到左以此降序的合唱序列，我们可以将这个数组进行反转，然后求出反转后的
    //序列从左到右的升序序列，就等于从右往左的降序序列。
    //但是在求出dp[j]数组后，需要将其重新反转回去，这样数据才是对应原先的位置。
    let dp2 = MaxList(arr.reverse()).reverse();
    let max = 0;
    //遍历dp数组，求出每个位置上dp1和dp2的值，由于自身参与了两次计算，因此还需要再
    //减去1，剪掉自身1次
    for (let i = 0; i 
 本文参考了牛客网的优质题解以及b站上up主的优质视频：
 
B站题解
 
牛客网链接