最长递增子序列 #326
Description
题目描述:
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例:
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路:DP
参考代码
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let n = nums.length, res = 0;
let f = new Array(n).fill(1)
for(let i = 0; i < n; i++)
for(let j = 0; j <=i; j++){
if(nums[j] < nums[i]){
f[i] = Math.max(f[i], f[j] + 1)
}
}
for(let i = 0; i < n; i++){
res = Math.max(f[i],res)
}
return res
};