题目
给你一个整数数组
nums，找到其中最长严格递增子序列的长度。
输入： nums = [10,9,2,5,3,7,101,18] 输出： 4 解释： 最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路一
这里题目要求是最长的递增数列的长度， 所以我们需要对每一个位置的最大长度进行统计，首先我们先声明一个dp变量，他是一个和形参nums同样长度的数组，默认每一位数都为1，然后我们使用循环，在循环中我们在套一层循环，在第二层循环中我们进行判断，如果形参nums数组j变量位置的数小于形参nums数组i变量的数，则使用Math.max方法在dp数组的i变量位置的数和dp数组的j变量位置的数自增1后取一个最大值，然后存在dp数组中i变量位置中，然后用Math.max方法将dp数组中的最大数查找出来并返回出去
var lengthOfLIS = function(nums) { let dp = new Array(nums.length).fill(1) for(let i=1;i<nums.length;i++) { for(let j=0;j<i;j++) { if(nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1) } } } return Math.max(...dp) };
思路二
我们先声明一个n变量用于存储形参nums的数据长度，然后判断n变量是否小于等于1，如果是则直接返回出去，如果不是我们声明一个tail数组，用于存放最长上升子序列，然后在使用循环，在循环中判断当前形参nums的某一项元素是否比tail数组中的最后一个大，如果是则使用push将形参nums的当前某项添加到tail数组中，如果不是则进行二分查找，最后将形参nums的数的当前项放到tail合适的位置中，让后面的数字与当前的数字形成上升子序列，最后把tail数据长度返回出去即可
var lengthOfLIS = function(nums) { let n = nums.length; if (n <= 1) { return n; } let tail = [nums[0]]; for (let i = 0; i < n; i++) { if (nums[i] > tail[tail.length - 1]) { tail.push(nums[i]); } else { let left = 0; let right = tail.length - 1; while (left < right) { let mid = (left + right) >> 1; if (tail[mid] < nums[i]) { left = mid + 1; } else { right = mid; } } tail[left] = nums[i]; } } return tail.length; };
