题目描述
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
思路&js代码
1、动态规划
var lengthOfLIS = function (nums) {
const dp = new Array(nums.length).fill(1) // values[i] 为以nums[i]结尾的最长子序列的长度
for (let i = 1; i < nums.length; i++) {
const tail = nums[i]
for (let j = 0; j < i; j++) {
if (nums[j] >= tail) continue
dp[i] = Math.max(dp[j] + 1, dp[i] || 1)
}
}
return Math.max(...dp)
};2、贪心
var lengthOfLIS = function (nums) {
if (nums.length === 0) return 0
const tails = [nums[0]]
for (let i = 1; i < nums.length; i++) {
/**
* 当遍历的数字大于tails的最后一项时，直接在末尾添加
* 否则，找到tails记录中，第一个大于该数字的记录，替换其值
*/
if (nums[i] > tails[tails.length - 1]) {
tails.push(nums[i])
} else {
const idx = getFirstIndex(tails, nums[i])
tails[idx] = nums[i]
}
}
function getFirstIndex(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] >= target) {
return i
}
}
}
return tails.length
}