当前位置：首页 > article >正文

数组的最长递减子序列

article 2024/11/16 17:54:57

求一个数组的最长递减子序列
如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
思路：动态规划
构建与原数组同等容量的辅助数组dp,记录以每个元素结束的最大序列的长度，如dp[0]=1,如果dp[i]<dp[i-1],则dp[i]=dp[i-1]+1，否则dp[i]=1；循环可求出dp数组。最终根据求出的dp数组最大值以及该值的索引按需截取子串即可！
最长递增子序列反推即可！

line = '9 5 4 3 2 5 4 3 1';
line = line.split(' ');
let n = line.length;
let res = [];
let dp = [];
dp[0] = 1;
//构造动态数组记录截止每个元素时的递减长度
for (let i = 1; i < n; i++) {
    if (line[i] < line[i - 1]) {
        dp[i] = dp[i - 1] + 1;
    } else {
        dp[i] = 1;
    }
}
//console.log('dp', dp);
let max = dp[0];//
let tag = 0;
//找出截止该元素最长递减子列表长度及及其所在位置索引
for (let i = 1; i < n; i++) {
    if (max <= dp[i]) {
        max = Math.max(max, dp[i]);
        //找出最长递减子列表长度的结束位置
        tag = i;
    }
}
//console.log('max', max);
//用substr截取即可，tag+1是为了防止出现-1
res = line.join('').substr(tag + 1 - max, max);
// res=line.slice(tag-max,tag);
//console.log('tag', tag);
console.log('res', res);