题解 | #合唱队#
合唱队
http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
const total = Number(readline());
const heights = readline().split(' ').map(Number);
// leftMaxAccList[i]表示，从左往右，以第i个人为中间时，包括他在内，他左边的最长递增子序列的长度
const leftMaxAccList = [];
for (let i = 0; i < total; i++) {
let m = 0;
for (let j = 0; j < leftMaxAccList.length; j++) {
if (heights[j] < heights[i]) {
m = Math.max(leftMaxAccList[j], m);
}
}
leftMaxAccList.push(m + 1);
}
// rightMaxAccList[i]表示，从右往左，以第i个人为中间时，包括他在内，他右边的最长递增子序列（从右往左递增）的长度
const rightMaxAccList = [];
for (let i = total - 1; i >= 0; i--) {
let m = 0;
let count = 1;
for (let j = rightMaxAccList.length - 1; j >= 0; j--) {
if (heights[total - count] < heights[i]) {
m = Math.max(rightMaxAccList[j], m);
}
count++;
}
rightMaxAccList.unshift(m + 1);
}
// 最长队形长度
let maxQueLen = 0;
for (let i = 0; i < total; i++) {
maxQueLen = Math.max(leftMaxAccList[i] + rightMaxAccList[i], maxQueLen);
}
// 用总数减去最长队列长度，就是最少要去掉的人数，因为每个位置上的人在求左边最长递增子序列和右边最长递增子序列时
// 都算了一遍，所以要减1
console.log(total - (maxQueLen - 1));
