子序列可以删除原序列中的部分元素，但必须保持剩余元素的相对顺序。它和子串不同，子串要求元素连续。

本文讨论两个经典问题：

  • LIS：一个序列中的最长严格递增子序列。
  • LCS：两个序列的最长公共子序列。

一、最长递增子序列 LIS

1.1 O(n^2) 动态规划

定义 dp[i] 为以 nums[i] 结尾的最长严格递增子序列长度。遍历 j < i，如果 nums[j] < nums[i]，就可以尝试使用 dp[j] + 1 更新 dp[i]：

dp[i] = max(1, dp[j] + 1)  (j < i 且 nums[j] < nums[i])

#include <algorithm>
#include <vector>

std::vector<int> LISQuadratic(const std::vector<int>& nums) {
  if (nums.empty()) {
    return {};
  }

  const int n = static_cast<int>(nums.size());
  std::vector<int> length(n, 1);
  std::vector<int> previous(n, -1);
  int best_end = 0;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (nums[j] < nums[i] && length[j] + 1 > length[i]) {
        length[i] = length[j] + 1;
        previous[i] = j;
      }
    }

    if (length[i] > length[best_end]) {
      best_end = i;
    }
  }

  std::vector<int> result;
  for (int current = best_end; current != -1;
       current = previous[current]) {
    result.push_back(nums[current]);
  }
  std::reverse(result.begin(), result.end());
  return result;
}

时间复杂度为 O(n^2)，空间复杂度为 O(n)。previous 数组记录前驱下标，因此不仅能得到长度，也能恢复一条具体的 LIS。

1.2 O(n log n) 求长度

维护数组 tails：

tails[k] 表示长度为 k + 1 的递增子序列的最小可能结尾值

遍历新元素时，使用 lower_bound 找到第一个大于等于它的位置并替换。对于严格递增序列必须使用 lower_bound；如果要求非递减序列，则使用 upper_bound。

#include <algorithm>
#include <vector>

int LISLength(const std::vector<int>& nums) {
  std::vector<int> tails;

  for (int value : nums) {
    auto position = std::lower_bound(
        tails.begin(), tails.end(), value);

    if (position == tails.end()) {
      tails.push_back(value);
    } else {
      *position = value;
    }
  }

  return static_cast<int>(tails.size());
}

tails 本身不一定是一条真实的 LIS，但它的长度就是 LIS 长度。时间复杂度为 O(n log n)，空间复杂度为 O(n)。

1.3 O(n log n) 恢复 LIS

如果还需要恢复序列，可以额外记录每个元素的下标以及它的前驱：

#include <algorithm>
#include <vector>

std::vector<int> LIS(const std::vector<int>& nums) {
  if (nums.empty()) {
    return {};
  }

  std::vector<int> tails;
  std::vector<int> tail_indices;
  std::vector<int> previous(nums.size(), -1);

  for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
    auto position = std::lower_bound(
        tails.begin(), tails.end(), nums[i]);
    const int length = static_cast<int>(
        position - tails.begin());

    if (length > 0) {
      previous[i] = tail_indices[length - 1];
    }

    if (position == tails.end()) {
      tails.push_back(nums[i]);
      tail_indices.push_back(i);
    } else {
      *position = nums[i];
      tail_indices[length] = i;
    }
  }

  std::vector<int> result;
  for (int current = tail_indices.back(); current != -1;
       current = previous[current]) {
    result.push_back(nums[current]);
  }
  std::reverse(result.begin(), result.end());
  return result;
}

二、最长公共子序列 LCS

2.1 动态规划求长度

定义 dp[i][j] 为 first 的前 i 个字符和 second 的前 j 个字符的最长公共子序列长度。

状态转移如下：

first[i - 1] == second[j - 1]
    dp[i][j] = dp[i - 1][j - 1] + 1

first[i - 1] != second[j - 1]
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

#include <algorithm>
#include <string_view>
#include <vector>

int LCSLength(std::string_view first, std::string_view second) {
  const int n = static_cast<int>(first.size());
  const int m = static_cast<int>(second.size());
  std::vector<std::vector<int>> dp(
      n + 1, std::vector<int>(m + 1, 0));

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (first[i - 1] == second[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[n][m];
}

时间复杂度为 O(nm)，空间复杂度为 O(nm)。

2.2 恢复一条 LCS

从 dp[n][m] 反向遍历：

  • 如果两个字符相等，它们属于一条 LCS，移动到左上角。
  • 如果不相等，移动到上方或左方较大的状态。
#include <algorithm>
#include <string>
#include <string_view>
#include <vector>

std::string LCS(std::string_view first, std::string_view second) {
  const int n = static_cast<int>(first.size());
  const int m = static_cast<int>(second.size());
  std::vector<std::vector<int>> dp(
      n + 1, std::vector<int>(m + 1, 0));

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (first[i - 1] == second[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  std::string result;
  int i = n;
  int j = m;
  while (i > 0 && j > 0) {
    if (first[i - 1] == second[j - 1]) {
      result.push_back(first[i - 1]);
      --i;
      --j;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      --i;
    } else {
      --j;
    }
  }

  std::reverse(result.begin(), result.end());
  return result;
}

如果只需要 LCS 的长度，可以将空间优化为 O(min(n, m))，只保留上一行和当前行；如果需要恢复路径，则通常需要保留完整的 dp 表，或者额外使用 Hirschberg 算法。

三、复杂度对比

问题 方法 时间复杂度 空间复杂度
LIS 长度 动态规划 O(n^2) O(n)
LIS 长度 tails + 二分 O(n log n) O(n)
LCS 长度 二维动态规划 O(nm) O(nm)
LCS 长度（只求长度） 滚动数组 O(nm) O(min(n, m))

四、总结

  • LIS 的 O(n^2) 动态规划适合推导和恢复路径。
  • LIS 的二分方法需要使用 lower_bound 处理严格递增序列。
  • tails 数组不一定本身构成一条 LIS，但其长度正确。
  • LCS 使用两个前缀序列的状态进行动态规划。
  • 恢复 LCS 需要根据动态规划表反向寻找路径。