37 lines
1020 B
JavaScript
37 lines
1020 B
JavaScript
function getSequence(arr) {
|
|
let maxLength = 0; // 记录最长递增子序列的长度
|
|
let maxSeq = []; // 记录最长递增子序列
|
|
|
|
let sequences = new Array(arr.length).fill().map(() => []);
|
|
|
|
// console.log(sequences);
|
|
|
|
// 遍历数组
|
|
for (let i = 0; i < arr.length; i++) {
|
|
// 创建一个以当前元素为结尾的递增子序列
|
|
let seq = [arr[i]];
|
|
// 遍历之前的元素，找到比当前元素小的元素，从而构建递增子序列
|
|
for (let j = 0; j < i; j++) {
|
|
if (arr[j] < arr[i]) {
|
|
// 把之前存储的序列和当前元素拼接起来
|
|
seq = sequences[j].concat(arr[i]);
|
|
}
|
|
}
|
|
|
|
// 将当前递增子序列存储起来
|
|
sequences[i] = seq;
|
|
|
|
// 更新最大的序列
|
|
if (seq.length > maxLength) {
|
|
maxLength = seq.length;
|
|
maxSeq = seq;
|
|
}
|
|
}
|
|
// console.log(sequences);
|
|
return maxSeq;
|
|
}
|
|
|
|
const list = [2, 1, 5, 3, 6, 4, 8, 9, 7];
|
|
const result = getSequence(list);
|
|
console.log(result); // [ 1, 3, 4, 8, 9 ]
|