*长上升子序列（JS实现）

\
1 题目
给定一个无序的整数数组，找到其中*长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: *长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种*长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

2 思路
这道题明显根据题意就知道应该用动态规划来做，注意题意，这里是子序列并不是要求连续的，设d[i]为0…i元素之间*大上升子序列长度，状态转移方程为 d[i+1] = max(d[0…i]) + 1

3代码
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
if (nums.length < 2) return nums.length;
const d = [1];

let maxAns = 1;
for (let i=1; i<nums.length; i++) {
let len = 0;
for (let j=0;j<d.length;j++) {
if (nums[i] > nums[j]) {
len = Math.max(len, d[j]);
}
}
d[i] = len + 1;
maxAns = Math.max(maxAns, d[i])
}

return maxAns;
};
、