最长递增子序列 (LIS)

算法

最长递增子序列是指在一个给定的数字序列中,找到一个子序列,使得这个子序列元素单调递增,并且长度尽可能大。该问题可以使用动态规划高效解决。

时间复杂度:最佳 O(n²) | 平均 O(n²) | 最差 O(n²)
空间复杂度:O(n)

应用场景/前提条件

  • 动态规划
  • 数组
  • 递增序列

算法讲解

最长递增子序列

介绍

最长递增子序列(Longest Increasing Subsequence, LIS)是一个经典的动态规划问题,目标是找出一个给定序列中最长的子序列,要求该子序列中的所有元素按照严格递增的顺序排列。注意,子序列不要求连续,但要保持原序列中元素的相对顺序。

最长递增子序列问题可以通过多种方法解决,其中动态规划是最为经典和直观的方法,时间复杂度为O(n²),n是序列长度。还有使用二分查找优化的方法可以将时间复杂度降低到O(n log n)。

算法步骤

  1. 定义状态:dp[i]表示以第i个元素结尾的最长递增子序列的长度
  2. 初始化:所有dp[i]初始值为1(至少包含自身一个元素)
  3. 状态转移:对于每个位置i,检查所有在它之前的位置j:
    • 如果nums[i] > nums[j],则可以将nums[i]接在以nums[j]结尾的子序列之后
    • dp[i] = max(dp[i], dp[j] + 1)
  4. 结果:max(dp[0], dp[1], ..., dp[n-1])

算法详解

为了更好地理解最长递增子序列的动态规划求解过程,我们以序列 [10, 9, 2, 5, 3, 7, 101, 18] 为例,详细分析整个计算流程:

初始化阶段

...