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)