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:
1
2
3
输入nums = [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4
  • 示例 2:
1
2
输入nums = [0,1,0,3,2,3]
输出4

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

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

2. 定义状态 #

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

3. 状态转移方程 #

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

对于满足 $0 \le 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] \le nums[i]$,则 $nums[i]$ 不可以接在 $nums[j]$ 后面,可以直接跳过。

综上,我们的状态转移方程为:$dp[i] = max(dp[i], dp[j] + 1),0 \le j < i,nums[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)$。
本站总访问量  次  |  您是本站第  位访问者