300-最长递增子序列.md

300-最长递增子序列

原题

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

输入：nums = [0,1,0,3,2,3] 输出：4

状态转移方程： 这道题比较直观，当问题的规模逐渐变大时候，取以 nums[i] 结尾的最长上升子序列集合最大值就可以了； 也就是以 nums[i]结尾，不断的去找前面比自己小的，这样就总能找出最长的了
就是不断的找前面比自己小的数，然后加 1，比较； 状态转移方程为： dp[i] = max(dp[i], dp[j] + 1); j < i 解题参考

const lengthOfLTS = function (nums) {
  let dp = Array.from({ length: nums.length }, () => 1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      /*
       * imp 没有明白这里的 nums[i] > nums[j] 的逻辑，
       *  递增子序列，是需要递增的，可是你这里直接比较 nums[i] 和 nums[j]
       *
       * imp 哦这里是在形成 dp[i] 的值
       * */
      if (nums[i] > nums[j]) {
        // 说实话我知道有检测当前这个 Math.max，但是就这样就可以了吗？沃日
        // 还是没太懂为什么要这样写
        // 明白了，看上面的状态转移方程的解释

        // 因为j 是从0 到i，所以dp[j]是知道的，但是这里的 Math.max(dp[i], dp[j] + 1)
        // 是什么意思，这里的 dp[i] 难道不是初始值 1 吗(打印了一下发现不是1)，为什么这里要使用 Math.max 呢

        // 为什么初始值要设置为1？因为本身就是一个长度，所以最小就是1
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  let max = 0;
  for (let i = 0; i < dp.length; i++) {
    max = Math.max(max, dp[i]);
  }

  return max;
};

let nums = [10, 9, 2, 5, 3, 7, 101, 18];
let result = lengthOfLTS(nums);
console.log(result);

思路 0. 其实这是一个从 1 开始的计算的，就是最小的长度就是 1

1. 然后就是使用一个 for 循环，从 0 到 i 中，dp 的每一位是如何设置的
2. 得到 dp 后，然后就是计算 dp 中最大的一位是多少

代码是简单，逻辑也不复杂，但也是总感觉有点绕