最长递增子序列意思是在一组数字中,找出最长一串递增的数字,比如
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 许可协议。转载请注明出处!