1. 题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

  1. 输入：nums = [10,9,2,5,3,7,101,18]
  2. 输出：4
  3. 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

  1. 输入：nums = [0,1,0,3,2,3]
  2. 输出：4

示例 3：

  1. 输入：nums = [7,7,7,7,7,7,7]
  2. 输出：1

提示：

  • 1 <= nums.length <= 2500
  • -10 <= nums[i] <= 10

进阶：

  • 你可以设计时间复杂度为 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. 代码实现

    1. /**
    2. * @param {number[]} nums
    3. * @return {number}
    4. */
    5. var lengthOfLIS = function(nums) {
    6.   const n = nums.length
    7.   if(!n){
    8.       return 0
    9.   }
    11.   let dp = new Array(n).fill(1)
    12.   for(let i = 1; i < n; i++){
    13.       for(let j = 0; j < i; j++){
    14.           if(nums[i] > nums[j]){
    15.               dp[i] = Math.max(dp[i], dp[j] + 1)
    16.           }
    17.       }
    18.   }
    19.   return Math.max(...dp)
    20. };

    4. 提交结果

    image.png