最长上升子序列(LIS)问题:给定长度为n的序列a,从a中抽取出一个子序列,这个子序列需要单调递增。问最长的上升子序列(LIS)的长度。
比如: 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8,长度为6。
x>p && Ax> Ap, f(x) = max(f(p)) + 1
const arr = [1,5,3,4,6,9,7,8];
function LIS(arr) {
let dp = [];
// 最长上升子序列,以i结尾的元素,其组成的LIS为dp[i]
arr.map((item, i) => {
dp[i] = 1;
for(let j= 0; j<i;j++) {
// 在原数组中,符合arr[i] > arr[j]的位置,找到使dp[j]最大的j, 则i = dp[j]+1;
if(arr[i]> arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
})
return Math.max.apply(null, dp);
}
倘若要输出这个最长的子序列内容呢?
let arr = [1, 9, 2, 7, 3, 6, 4, 5];
function LIS(arr) {
let dp = [];
let obj = {} // 保存以i结尾的元素所对应的最长子序列
// 最长上升子序列,以i结尾的元素,其组成的LIS为dp[i]
arr.map((item, i) => {
dp[i] = 1;
obj[i] = [item];
for(let j= 0; j<i;j++) {
// 在原数组中,符合arr[i] > arr[j]的位置,找到使dp[j]最大的j, 则i = dp[j]+1;
if(arr[i]> arr[j] && (dp[j] + 1) > dp[i]) {
dp[i] = dp[j] + 1;
obj[i] = obj[j].concat([item]);
}
}
})
const maxLen = Math.max.apply(null, dp);
const index = dp.indexOf(maxLen);
return obj[index];
}
如果是最长连续上升子序列(LCIS)呢?
因为要考虑连续,没有最优子结构,没法用动态规划的思想了,一个遍历中比较得到结果。
function LCIS(arr) {
let count =1;
let max = 1;
let countArr = [];
let cis=[arr[0]];
for(let i=0,len = arr.length; i<len-1;i++) {
if(arr[i]<arr[i+1]) {
count++;
countArr.push(arr[i])
} else {
if(count > max) {
max = count;
countArr.push(arr[i]);
cis = [...countArr];
}
count = 1;
countArr = [];
}
}
return cis;
}
https://juejin.im/post/5b0c2583f265da08f50b4b33#heading-10
/**
* 最长公共子序列
* if(arr1[i] === arr2[j]) {
* res[i][j] = res[i-1][j-1]+1
* } else {
* res[i][j] = Math.max(res[i-1][j], res[i][j-1])
*
* 注意的是:倘若str1='adfghc',转化为arr1 = str1.split('').unshift(' '); 为了辅助计算,需要在转化为的数组前加一个空串。
* 原因: 根据如上的最优子结构,我们需要为其提供初始值,如果没有添加空串作为辅助,我们就要计算出第一行,第一列左右位置的值。添加辅助之后,直接第一行和第一列都赋值为0即可
* }
*/
function LCS(str1, str2) {
const arr1 = [''].concat(str1.split(''))
const arr2 = [''].concat(str2.split(''))
console.log('arr1', arr1);
console.log('arr2', arr2);
let res = [];
let len1=arr1.length;
let len2=arr2.length;
for(let i=0; i<len1;i++) {
res[i] = [];
for(let j=0; j<len2;j++) {
if(i===0 || j === 0) {
res[i][j] = 0;
continue;
}
if(arr1[i] === arr2[j]) {
res[i][j] = res[i-1][j-1]+1;
} else {
res[i][j] =Math.max(res[i-1][j], res[i][j-1]);
}
}
}
console.log('res', res);
}
求 连续子序列最大和
定义以第i位结尾的数字,其连续序列最大和为sum[i]
最优子结构: sum[i] = max({sum[i-1] + arr[i], arr[i]})
function LCSS(arr) {
let sum = [];
const len = arr.length;
sum[0] = arr[0];
for(let i=1; i<len; i++) {
sum[i] = arr[i];
if(sum[i-1]>0) {
sum[i] = sum[i-1] + arr[i]
}
}
return Math.max(...sum);
}
网友评论