2021-01-26 | 300. 最长递增子序列

梦里梦外; 2022-10-29 11:30 23阅读 0赞

### 1. 题目描述 ###

给你一个整数数组 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

提示：

*  1 <= nums.length <= 2500
 *  \-104 <= nums\[i\] <= 104

进阶：

*  你可以设计时间复杂度为 O(n2) 的解决方案吗？
 *  你能将算法的时间复杂度降低到 O(n log(n)) 吗?

### 2. 解题思路 ###

碰到子序列的问题，我们最容易想到的就是动态规划。

首先初始化一个数组dp来保存每个子问题的最优解，dp\[i\]表示数组前n的元素的最长连续子序列，最后返回所有子序列中最长的序列就可以了。

**复杂度分析：**

*  **时间复杂度**：O(n)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp\[i\] 时，需要 O(n) 的时间遍历dp\[0…i−1\] 的所有状态，所以总时间复杂度为 O(n)。
 *  **空间复杂度**：O(n)，需要额外使用长度为 n 的 dp 数组。

### 3. 代码实现 ###

/** * @param {number[]} nums * @return {number} */
    var lengthOfLIS = function(nums) { 
        const n = nums.length
        if(!n){ 
            return 0
        }
    
        let dp = new Array(n).fill(1)
        for(let i = 1; i < n; i++){ 
            for(let j = 0; j < i; j++){ 
                if(nums[i] > nums[j]){ 
                    dp[i] = Math.max(dp[i], dp[j] + 1)
                }
            }
        }
        return Math.max(...dp)
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210214000235683.png]

[20210214000235683.png]: /images/20221024/16ef10016ca74eca977e51e20c6befab.png?