最长递增子序列的长度

题目

最长递增子序列的长度

信息

• 类型：问答
• 难度：⭐⭐

考点

动态规划设计,状态转移方程,算法优化

快速回答

给定一个整数数组，求最长严格递增子序列的长度。解决方案：

• 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
• 初始化所有 dp[i] = 1（每个元素自身构成子序列）
• 状态转移：dp[i] = max(dp[i], dp[j] + 1) 当 j < i 且 nums[j] < nums[i]
• 最终结果为 max(dp)
• 时间复杂度 O(n²)，空间复杂度 O(n)

问题描述

给定一个整数数组 nums，找到其中最长的严格递增子序列的长度。子序列不要求连续，但必须保持原始顺序。例如：
输入 [10,9,2,5,3,7,101,18] 输出 4（最长子序列 [2,5,7,101]）

原理说明

动态规划的核心思想：
1. 状态定义：dp[i] 表示以第 i 个元素结尾的最长递增子序列长度
2. 状态转移：对于每个位置 i，遍历所有 j < i：
- 若 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)
3. 初始化：每个元素自身构成长度为1的子序列，故 dp[i] = 1
4. 最终解：max(dp)（最长子序列不一定以最后一个元素结尾）

代码示例

def lengthOfLIS(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 测试用例
print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # 输出 4

最佳实践

• 边界处理：空数组直接返回0
• 优化方案：对于大型数组（n>1000），可用二分查找优化到 O(n log n)：

  def lengthOfLIS_optimized(nums):
      tails = []
      for num in nums:
          # 二分查找插入位置
          left, right = 0, len(tails)
          while left < right:
              mid = (left + right) // 2
              if tails[mid] < num:
                  left = mid + 1
              else:
                  right = mid
          if left == len(tails):
              tails.append(num)
          else:
              tails[left] = num
      return len(tails)

• 方法选择：面试中先实现基础DP，再讨论优化

常见错误

• 错误初始化：忘记将 dp 数组初始化为1
• 转移条件错误：遗漏 nums[j] < nums[i] 的判断
• 结果获取错误：返回 dp[-1] 而非 max(dp)
• 理解偏差：混淆子序列（不连续）与子数组（连续）

扩展知识

• 输出具体序列：额外使用 prev 数组记录转移路径，最后回溯重构序列
• 变种问题：
  - 最长非递减子序列（允许相等）
  - 俄罗斯套娃信封问题（二维LIS）
  - 最长递增子序列的数量统计
• 实际应用：基因序列比对、股票趋势分析、路由优化