本文共 1495 字，大约阅读时间需要 4 分钟。
最长递增子序列（Longest Increasing Subsequence，LIS）问题是算法中的经典难题之一。它的核心目标是找到一个数组中最长且严格递增的子序列。简而言之，就是在一个整数数组中，找到一个尽可能长的序列，使得每个元素都比前一个元素大。
为了找到最长递增子序列，我们可以使用动态规划（Dynamic Programming）的方法。这种方法通过维护一个额外的数组（通常称为 dp 数组）来记录每个位置的最长递增子序列的长度。
初始化 dp 数组：创建一个与原数组长度相同的 dp 数组，初始值均为 1。因为每个元素本身都可以看作是一个长度为 1 的子序列。
填充 dp 数组：对于数组中的每一个元素，遍历之前所有元素。如果当前元素大于之前某个元素，那么当前元素的子序列长度可以取决于之前那个元素的子序列长度加 1。
记录最长长度：在整个填充过程中，记录最大的 dp 数组值，这就是最长递增子序列的长度。
以下是具体的代码实现：
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[i] > nums[j]: if dp[i] < dp[j] + 1: dp[i] = dp[j] + 1 return max(dp)
dp 数组初始化：数组 dp 的长度与输入数组 nums 相同，每个元素初始值都为 1。
双重循环遍历数组：外层循环遍历数组中的每一个元素 nums[i]，内层循环遍历之前的每一个元素 nums[j]（其中 j < i）。
比较元素大小：如果当前元素 nums[i] 大于之前的元素 nums[j]，则更新 dp[i] 的值为 dp[j] + 1。这里需要注意的是，取最大值是为了保证 dp[i] 处存储的值是最优的。
返回结果：最后，取 dp 数组中的最大值作为结果，这个值即为最长递增子序列的长度。
假设输入数组为 [3, 1, 2, 4]，则最长递增子序列的长度为 3。具体步骤如下：
初始化 dp 数组为 [1, 1, 1, 1]。
遍历每个元素：
3（索引 0），没有前面的元素，dp[0] 保持为 1。1（索引 1），与 3 比较，1 < 3，但 dp[1] 保持为 1。2（索引 2），与 3 比较，2 < 3，所以 dp[2] 不更新；与 1 比较，2 > 1，所以 dp[2] 更新为 dp[1] + 1 = 2。4（索引 3），与 3 比较，4 > 3，所以 dp[3] 更新为 dp[0] + 1 = 2；与 1 比较，4 > 1，dp[3] 更新为 dp[1] + 1 = 2；与 2 比较，4 > 2，dp[3] 更新为 dp[2] + 1 = 3。最终 dp 数组为 [1, 1, 2, 3]，最大值为 3，即最长递增子序列的长度为 3。
这个算法的时间复杂度为 O(n^2)，在处理较大规模的数组时可能会显得较慢。因此，人们通常会寻找更高效的算法，比如使用二分查找优化后的 O(n log n) 解决方案。
转载地址：http://fdsl.baihongyu.com/