0300. 最长递增子序列

0300. 最长递增子序列 #

  • 标签:二分查找、动态规划
  • 难度:中等

题目大意 #

描述:给定一个整数数组 nums

要求:找到其中最长严格递增子序列的长度。

说明

  • 子序列:由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
  • $1 \le nums.length \le 2500$。
  • $-10^4 \le nums[i] \le 10^4$。

示例

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

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

按照子序列的结尾位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为:以 nums[i] 结尾的最长递增子序列长度。

3. 状态转移方程 #

一个较小的数后边如果出现一个较大的数,则会形成一个更长的递增子序列。

对于满足 0 <= j < i 的数组元素 nums[j]nums[i] 来说:

  • 如果 nums[j] < nums[i],则 nums[i] 可以接在 nums[j] 后面,此时以 nums[i] 结尾的最长递增子序列长度会在「以 nums[j] 结尾的最长递增子序列长度」的基础上加 1,即 dp[i] = dp[j] + 1

  • 如果 nums[j] >= nums[i],则 nums[i] 不可以接在 nums[j] 后面,可以直接跳过。

综上,我们的状态转移方程为:dp[i] = max(dp[i], dp[j] + 1)0 <= j <= inums[j] < nums[i]

4. 初始条件 #

默认状态下,把数组中的每个元素都作为长度为 1 的递增子序列。即 dp[i] = 1

5. 最终结果 #

根据我们之前定义的状态,dp[i] 表示为:以 nums[i] 结尾的最长递增子序列长度。那为了计算出最大的最长递增子序列长度,则需要再遍历一遍 dp 数组,求出最大值即为最终结果。

思路 1:动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [1 for _ in range(size)]

        for i in range(size):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

思路 1:复杂度分析 #

  • 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,最后求最大值的时间复杂度是 $O(n)$,所以总体时间复杂度为 $O(n^2)$。
  • 空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。
本站总访问量  次  |  您是本站第  位访问者