2022-09-17算法00
请注意,本文编写于 617 天前,最后修改于 617 天前,其中某些信息可能已经过时。

最长递增子序列

最长递增子序列意思是在一组数字中,找出最长一串递增的数字,比如

0, 3, 4, 17, 2, 8, 6, 10

对于以上这串数字来说,最长递增子序列就是 0, 3, 4, 8, 10,可以通过以下表格更清晰的理解

| 数字 | 0 | 3 | 4 | 17 | 2 | 8 | 6 | 10 | | 长度 | 1 | 2 | 3 | 4 | 2 | 4 | 4 | 5 |

通过以上表格可以很清晰的发现一个规律,找出刚好比当前数字小的数,并且在小的数组成的长度基础上加一。

这个问题的动态思路解法很简单,直接上代码

function lis(n) {
  if (n.length === 0) return 0
  // 创建一个和参数相同大小的数组,并填充值为 1
  let array = new Array(n.length).fill(1)
  // 从索引 1 开始遍历,因为数组已经所有都填充为 1 了
  for (let i = 1; i < n.length; i++) {
    // 从索引 0 遍历到 i
    // 判断索引 i 上的值是否大于之前的值
    for (let j = 0; j < i; j++) {
      if (n[i] > n[j]) {
        array[i] = Math.max(array[i], 1 + array[j])
      }
    }
  }
  let res = 1
  for (let i = 0; i < array.length; i++) {
    res = Math.max(res, array[i])
  }
  return res
}

本文作者:毛超颖

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!