43 lines
1.2 KiB
JavaScript
43 lines
1.2 KiB
JavaScript
function getSequence(arr) {
|
|
let maxLength = 0; // 记录最长递增子序列的长度
|
|
let longetSeq = []; // 记录最长递增子序列
|
|
|
|
/**
|
|
*
|
|
* @param {*} index 列表的下标
|
|
* @param {*} subSeq 当前递增子序列
|
|
*/
|
|
function findSubsequence(index, subSeq) {
|
|
let currentNum = arr[index]; // 当前元素
|
|
// 先把之前的递增子序列展开，再加上当前元素
|
|
let newSeq = [...subSeq, currentNum]; // 新的递增子序列
|
|
|
|
// 遍历下标之后的内容
|
|
for (let i = index + 1; i < arr.length; i++) {
|
|
// 遍历当前下标之后的元素时，发现有比当前元素大的元素
|
|
if (arr[i] > currentNum) {
|
|
findSubsequence(i, newSeq);
|
|
}
|
|
}
|
|
|
|
// 每一次递归结束后，就会得到一个新的递增子序列
|
|
// 相当于找到了所有的递增子序列
|
|
// console.log("newSeq:", newSeq);
|
|
|
|
if (newSeq.length > maxLength) {
|
|
maxLength = newSeq.length;
|
|
longetSeq = newSeq;
|
|
}
|
|
}
|
|
|
|
for (let i = 0; i < arr.length; i++) {
|
|
findSubsequence(i, []);
|
|
}
|
|
|
|
return longetSeq;
|
|
}
|
|
|
|
const list = [2, 1, 5, 3, 6, 4, 8, 9, 7];
|
|
const result = getSequence(list);
|
|
console.log(result);
|