LeetCode 300: 最长递增子序列 — 逐步可视化追踪

Source: Dev.to

问题描述

在整数数组中找到最长严格递增子序列的长度。子序列保持元素的相对顺序，但不要求连续。

思路

使用动态规划，其中 dp[i] 表示以索引 i 结尾的最长递增子序列的长度。
对每个元素，检查所有之前的元素，如果当前元素更大，则可以在它们的子序列基础上延伸。

复杂度

• 时间复杂度: O(n²)
• 空间复杂度: O(n)

代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        # Initialize a dynamic programming array dp with all values set to 1.
        dp = [1] * len(nums)

        # Iterate through the array to find the longest increasing subsequence.
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # Return the maximum value in dp, which represents the length of the longest increasing subsequence.
        return max(dp)

可视化

打开交互式可视化：打开 TraceLit 并逐行执行代码。
使用 TraceLit 构建——LeetCode 练习的可视化算法追踪工具。