0300. 最长递增子序列

0300. 最长递增子序列 #

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

题目大意 #

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

解题思路 #

用动态规划来做。

动态规划的状态 dp[i] 表示为:以第 i 个数字结尾的前 i 个元素中最长严格递增子序列的长度。

遍历前 i 个数字,0 ≤ j ≤ i:

  • 当 nums[j] < nums[i] 时,nums[i] 可以接在 nums[j] 后面,此时以第 i 个数字结尾的最长严格递增子序列长度 + 1,即 dp[i] = dp[j] + 1。
  • 当 nums[j] ≥ nums[i] 时,可以直接跳过。

则状态转移方程为:dp[i] = max(dp[i], dp[j] + 1),0 ≤ j ≤ i,nums[j] < nums[i]。

最后再遍历一遍 dp 数组,求出最大值即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [0 for _ in range(size)]
        for i in range(size):
            dp[i] = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
本站总访问量  次  |  您是本站第  位访问者