各种最x子序列

最长上升子序列（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);
}