题解 | #合唱队# 使用动态规划处理最多下降子序列
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4?tpId=37&tqId=21247&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=%E5%90%88%E5%94%B1
const rl = require("readline").createInterface({ input: process.stdin, output: process.stdout, }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { let dataArr = []; let N = 0; while ((line = await readline())) { // 请最少的同学(N-K)出列, 剩下的人排成合唱队 // 存在一位同学, 左侧递增,右侧递减(K最大) dataArr.push(line); const len = dataArr.length; // 处理多行输入 if (len == 1) { N = Number(dataArr[0]); } else { // 需要把输入的字符串转成数字 resultArr = dataArr[1].split(" ").map(item => Number(item)); // dp1 dp2表示左右两侧的动态规划 // 1.左右两侧的下降子序列 // 2.找到中心点 const n = resultArr.length; const dp1 = new Array(n).fill(0); const dp2 = new Array(n).fill(0); // 左侧下降子序列 for (let i = 0; i < n; i++) { // dp1 => 左侧符合条件的个数 (递增) dp1[i] = 1; for (let j = 0; j < i; j++) { if (resultArr[i] > resultArr[j]) { dp1[i] = Math.max(dp1[i], dp1[j] + 1); } } } for (let i = n - 1; i >= 0; i--) { // dp2 => 右侧符合条件的个数 (递减) dp2[i] = 1; for (let j = n - 1; j > i; j--) { if (resultArr[i] > resultArr[j]) { dp2[i] = Math.max(dp2[i], dp2[j] + 1); } } } let max = 0 for (let i = 0; i < n; i++) { // 找核心点 if (max <= dp1[i] + dp2[i] - 1) { max = dp1[i] + dp2[i] - 1 } } console.log(N - max) } } })();