最长递增子序列.md

最长递增子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：

 输入: [10,9,2,5,3,7,101,18]
 输出: 4 
 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明：

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n^2) 。

解题思路

参考数学归纳法思路
根据第1，...，i - 1个数结尾的最长递增子序列的长度计算得到第i个数结尾的最长递增子序列的长度
最后得到全部以第i个数结尾的最长递增子序列的长度
在这些长度中的最大值就是最大长度了

var lengthOfLIS = function(list) {
  // dp[i] 表示以 list[i] 这个数结尾的最长递增子序列的长度
  const dp = Array(list.length).fill(1)
  for (let i = 1; i < list.length; i++) {
    for (let j = 0; j < i; j++) {
      // 找到前面小于自己的数
      if (list[i] > list[j]) {
        // 自然能够形成dp[j] + 1的长度，取最长的一次
        dp[i] = Math.max(dp[j] + 1, dp[i])
      }
    }
  }
  let max = 1
  for (let i = 1; i < list.length; i++) {
    max = Math.max(max, dp[i])
  }
  return max
}