【leetcode】300. 最长递增子序列js

题目动态规划dp[i]含义是前i个元素最长子序列的长度。初始情况下dp数组所有元素赋值1。当遍历到nums[i]去找前面比当前值小的nums[j]dp[i] dp[j] 1又因为是要找到以当前nums[i]为结尾的最长的子序列所以遍历前面全部的nums[j]dp[i]要取最大的的dp[j]然后加上1因此代码中要作比较保存最大值。/** * param {number[]} nums * return {number} */ var lengthOfLIS function(nums) { const dp new Array(nums.length).fill(1) let res 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) } res Math.max(res, dp[i]) } return res };遍历整个dp时间复杂度为O(n)算出每个dp[i]时间复杂度为O(n)总时间复杂度为O(n²)。空间复杂度为O(n)。