1. 问题定义

给定一个数字序列（数组），找到其一个最长的子序列，要求这个子序列中的所有元素都是单调递增的。我们通常要求的是这个最长递增子序列的长度。

例如，给定序列 [10, 9, 2, 5, 3, 7, 101, 18]

• 它的一些递增子序列有：[2, 5, 7, 101], [2, 3, 7, 18], [9, 101], [10, 101] 等。
• 其中最长的递增子序列是 [2, 5, 7, 101] 或 [2, 3, 7, 101] 或 [2, 3, 7, 18] 等，它们的长度都是 4。
• 所以，对于这个输入，问题的解是 4。

2. 核心概念辨析：子序列 vs. 子数组

这是一个非常关键的区别，也是初学者容易混淆的地方。

• 子数组 (Subarray) / 子串 (Substring)：必须是原序列中连续的一部分。
  • 对于 [10, 9, 2, 5]，[9, 2] 是一个子数组，但 [10, 2] 不是。
• 子序列 (Subsequence)：可以不连续，但必须保持元素在原序列中的相对顺序。
  • 对于 [10, 9, 2, 5]，[10, 2, 5] 是一个子序列。我们从原序列中“挑选”了第1、3、4个元素，它们的相对顺序没有改变。

LIS 问题研究的是子序列。

3. 解法一：动态规划 (O(n²))

这是解决 LIS 问题最经典、最容易理解的方法。

核心思想

定义一个 dp 数组，dp[i] 表示以 nums[i] 这个元素结尾的最长递增子序列的长度。

为了计算 dp[i]，我们需要回头看 i 之前的所有元素 nums[j] (其中 j < i)。

• 如果 nums[i] > nums[j]，这意味着 nums[i] 可以接在以 nums[j] 结尾的递增子序列的后面，形成一个更长的递增子序列。
• 这个新的长度就是 dp[j] + 1。
• 由于可能有多个 j 满足 nums[i] > nums[j]，我们要选择能使新序列最长的那一个。

状态转移方程

dp[i] = max(dp[j] + 1)，其中 0 <= j < i 且 nums[i] > nums[j]。

如果找不到任何 j 满足条件，说明 nums[i] 比前面的所有数都小，它只能自己构成一个长度为 1 的递增子序列。所以 dp[i] 的初始值（或基础情况）为 1。

最终的答案是整个 dp 数组中的最大值，因为最长递增子序列可能在任何位置结束。

步骤详解

以 [10, 9, 2, 5, 3, 7, 101, 18] 为例：

1. i = 0, nums[0] = 10
   • dp[0] = 1 (自身构成长度为1的序列)
2. i = 1, nums[1] = 9
   • j=0: nums[1] (9) 不大于 nums[0] (10)。
   • dp[1] = 1
3. i = 2, nums[2] = 2
   • j=0,1: nums[2] (2) 都不大于 nums[0](10) 和 nums[1](9)。
   • dp[2] = 1
4. i = 3, nums[3] = 5
   • j=0: nums[3](5) < nums[0](10)。
   • j=1: nums[3](5) < nums[1](9)。
   • j=2: nums[3](5) > nums[2](2)。可以接在后面，长度为 dp[2] + 1 = 1 + 1 = 2。
   • dp[3] = 2
5. i = 4, nums[4] = 3
   • j=2: nums[4](3) > nums[2](2)。长度为 dp[2] + 1 = 2。
   • dp[4] = 2
6. i = 5, nums[5] = 7
   • j=2: nums[5](7) > nums[2](2) -> dp[2]+1=2
   • j=3: nums[5](7) > nums[3](5) -> dp[3]+1=3
   • j=4: nums[5](7) > nums[4](3) -> dp[4]+1=3
   • 取最大值，dp[5] = 3
7. … 以此类推 …

最后得到的 dp 数组会是 [1, 1, 1, 2, 2, 3, 4, 4]。 这个数组的最大值是 4，即为 LIS 的长度。

复杂度分析

• 时间复杂度: O(n²)。外层循环 i 从 0 到 n-1，内层循环 j 从 0 到 i-1，是两层嵌套循环。
• 空间复杂度: O(n)。需要一个 dp 数组来存储中间状态。

4. 解法二：贪心 + 二分查找 (O(n log n))

这个解法更巧妙，也更高效。

核心思想

我们维护一个数组 tails (或叫 min_end)，其中 tails[i] 存储的是所有长度为 i+1 的递增子序列中，结尾元素的最小值。

这个定义非常关键。举个例子，假设我们有两个长度为 3 的递增子序列 [2, 4, 8] 和 [1, 5, 6]。tails[2] (长度为3) 应该存储 6 而不是 8。为什么？因为结尾元素越小，后面能接上新元素的可能性就越大，这个序列就“更有潜力”。

基于这个思想，我们遍历原数组 nums：

1. 如果 num 大于 tails 数组中所有元素（即 num > tails.back()），说明 num 可以接在目前最长的递增子序列后面，形成一个更长的序列。我们就把 num 添加到 tails 的末尾，LIS 的长度加一。

2. 如果 num 不大于 tails 数组中所有元素，说明它不能让 LIS 变得更长。但是，它有可能“优化”现有的 tails 数组。我们在 tails 数组中找到第一个大于或等于 num 的元素，然后用 num 替换它。

   • 这步操作的意义是：我们找到了一个可以构成同样长度的递增子序列的、但结尾更小的元素。这使得未来的扩展可能性更大。

由于 tails 数组在整个过程中始终是有序的，所以“查找第一个大于或等于 num 的元素”这个操作可以用二分查找来完成，从而将时间复杂度降低。

最终，tails 数组的长度就是 LIS 的长度。注意：tails 数组本身并不是一个 LIS 序列！

步骤详解

以 [10, 9, 2, 5, 3, 7, 101, 18] 为例：

1. num = 10: tails 为空，直接加入。 tails = [10]
2. num = 9: 9 不大于 10。在 tails 中找到第一个大于等于 9 的数是 10，替换它。 tails = [9]
3. num = 2: 2 不大于 9。替换 9。 tails = [2]
4. num = 5: 5 大于 tails 的最后一个元素 2。直接加入。 tails = [2, 5]
5. num = 3: 3 不大于 5。在 tails 中找到第一个大于等于 3 的数是 5，替换它。 tails = [2, 3]
6. num = 7: 7 大于 tails 的最后一个元素 3。直接加入。 tails = [2, 3, 7]
7. num = 101: 101 大于 7。直接加入。 tails = [2, 3, 7, 101]
8. num = 18: 18 不大于 101。在 tails 中找到第一个大于等于 18 的数是 101，替换它。 tails = [2, 3, 7, 18]

遍历结束，tails 数组的长度为 4。这就是 LIS 的长度。

复杂度分析

• 时间复杂度: O(n log n)。遍历 nums 数组需要 O(n)，每次遍历都在 tails 数组上执行一次二分查找，tails 的长度最多为 n，所以二分查找的复杂度是 O(log n)。
• 空间复杂度: O(n)。需要 tails 数组存储状态。

5. 两种解法的对比总结

6. 如何输出最长递增子序列本身？

我们上面的讨论主要集中在求长度。如果要求输出序列本身，可以对 O(n²) 的 DP 解法进行扩展。

方法： 在计算 dp 数组的同时，再维护一个 parent 数组。parent[i] 记录的是构成以 nums[i] 结尾的 LIS 时，nums[i] 的前一个元素的索引。

1. 在计算 dp[i] 时，当我们找到一个 j 使得 dp[i] = dp[j] + 1，我们就记录 parent[i] = j。
2. 计算完所有 dp 值后，找到 dp 数组中最大值的索引，设为 end_index。这个 nums[end_index] 就是 LIS 的最后一个元素。
3. 通过 parent 数组向前回溯：从 end_index 开始，不断地访问 parent[end_index]，再 parent[parent[end_index]]… 直到找到一个没有父节点的元素。将这个路径上的所有元素收集起来，再反转，就是 LIS 之一。

对于 O(n log n) 的解法，要输出序列会更复杂一些，通常需要额外记录每个数字插入 tails 数组时的前驱信息，不如 DP 方法来得直接。因此，如果需要输出序列，使用 O(n²) 的 DP 方法并加以改造是更常见的选择。