1. 题目描述：最长递增子序列（LIS）

给定一个整数数组 nums，要求返回其中 最长严格递增子序列（Longest Increasing Subsequence, LIS）的长度。leetcode​

• 严格递增：后一个元素必须 大于 前一个元素，不能相等。
• 子序列：从原数组中按顺序选择若干元素，可以不连续，但相对顺序不能变。leetcode​

示例：leetcode​

示例 1：

输入：[10,9,2,5,3,7,101,18]
输出：4
解释：一个 LIS 是 [2,3,7,101]，长度为 4。

示例 2：

输入：[0,1,0,3,2,3]
输出：4

示例 3：

输入：[7,7,7,7,7,7,7]
输出：1。[leetcode](https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150)​

约束：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4。leetcode​

进阶：能否在 O(n log n) 时间复杂度内求解？leetcode​

---

2. O(n²) 动态规划：经典解法

2.1 状态定义

用一维数组 dp，定义如下：leetcode​

dp[i]：以 nums[i] 结尾 的最长严格递增子序列的长度。

为什么这样定义？

LIS 一定以某个位置结尾，把“结尾固定在 i”后，就能尝试接在它前面所有比它小的元素后面，做状态转移。leetcode​

2.2 初始化

至少可以选自己一个元素构成长度为 1 的 LIS，所以：leetcode​

对所有 i，令 dp[i] = 1。

2.3 状态转移

对每个位置 i，枚举它前面所有位置 j（0 ≤ j < i）：leetcode​

• 如果 nums[i] > nums[j]，则可以把 nums[i] 接到以 j 结尾的递增子序列后面：

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

伪代码：

dp[0..n-1] = 1
for i in [0..n-1]:
    for j in [0..i-1]:
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp[0..n-1])

最后答案是 dp 数组中的最大值，因为 LIS 可以以任意位置结尾。leetcode​

2.4 C 代码实现（O(n²)）

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int *dp = (int *)malloc(sizeof(int) * numsSize);
    int ans = 1;

    // 初始化：每个位置至少为 1
    for (int i = 0; i < numsSize; ++i) {
        dp[i] = 1;
    }

    // 双层循环转移
    for (int i = 0; i < numsSize; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        if (dp[i] > ans) ans = dp[i];
    }

    free(dp);
    return ans;
}

时间复杂度：外层 n，内层最坏 n，总共 O(n²)；空间复杂度 O(n)。leetcode​

---

3. O(nlogn) 解法：二分 + tail 数组

O(n²) 的瓶颈在于：对每个 i 都要枚举所有 j < i，也就是一个“DP + 枚举前面所有状态”的模式。优化思路是：不再关心每个 i 的 dp 值，而是维护“每种长度的 LIS 的最优状态”。leetcode​

3.1 核心思想：维护最小结尾数组 tail

定义一个数组 tail：leetcode​

tail[len - 1]：表示长度为 len 的所有严格递增子序列中，结尾元素最小 的那个结尾值。

例如某一时刻：

• tail[0] = 2：存在长度为 1 的递增子序列，结尾最小可以是 2。
• tail[1] = 3：存在长度为 2 的递增子序列，结尾最小可以是 3。
• tail[2] = 7：存在长度为 3 的递增子序列，结尾最小可以是 7。
• tail[3] = 18：存在长度为 4 的递增子序列，结尾最小可以是 18。leetcode​

这里我们并不关心“具体是哪条序列”，只关心对于每个长度 len，最小结尾是多少，因为：

• 对同样长度 len 的两个递增子序列，结尾越小越有潜力 被接上更多后续元素；
• 所以同一长度只需要保留“结尾最小”的那一个，其它可以全部丢掉。leetcode​

同时可以证明：tail 数组本身是单调递增的（长度越长，结尾最小值越大或相等，但在 LIS 严格递增的场景下，会呈现递增结构）。leetcode​

3.2 对每个 nums[i] 要做什么？

遍历 nums，对每一个新元素 x = nums[i] 做如下操作：leetcode​

1. 在 tail[0..len-1] 中用 二分查找 找到第一个 >= x 的位置 pos。
2. 如果这样的 pos 存在：
   • tail[pos] 代表某个长度为 pos+1 的递增子序列的最小结尾；
   • 用 x 替换它：tail[pos] = x，因为 x <= tail[pos]，新的结尾更小，更优。
3. 如果不存在（即 x 大于 tail 中所有元素）：
   • 说明可以在当前最长 LIS 的后面接上 x，长度 len + 1：
   • tail[len] = x，然后 len++。leetcode​

注意这里是 替换，而不是插入：

• 对某个固定长度 k，我们只需要记录“一个最优结尾值”，替换旧值是用更好的状态覆盖掉差的状态；
• 没必要为同一个长度保留多种结尾值，保留最小那个即可，对后续扩展来说是“支配”的。leetcode​

3.3 示例推导

以 nums = [10,9,2,5,3,7,101,18] 为例：leetcode​

初始：tail = [], len = 0
x = 10：tail = [10], len = 1
x = 9：第一个 >= 9 是 10，替换 → [9]
x = 2：第一个 >= 2 是 9，替换 → [2]
x = 5：找 >= 5，不存在（2 < 5），追加 → [2, 5], len = 2
x = 3：第一个 >= 3 是 5，替换 → [2, 3]
x = 7：找 >= 7，不存在（2,3 < 7），追加 → [2, 3, 7], len = 3
x = 101：追加 → [2, 3, 7, 101], len = 4
x = 18：第一个 >= 18 是 101，替换 → [2, 3, 7, 18]。[leetcode](https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150)​

最终 len = 4，就是 LIS 长度。真实 LIS 可以是 [2,3,7,101] 或 [2,3,7,18]，但题目只要长度即可。leetcode​

3.4 伪代码

tail[0..n-1]  // 用来维护每个长度的最小结尾
len = 0       // 当前已知 LIS 的长度

for x in nums:
    // 在 tail[0..len-1] 中找第一个 >= x 的位置 pos
    pos = lower_bound(tail, 0, len, x)

    if pos == len:
        // x 大于所有结尾，LIS 长度 + 1
        tail[len] = x
        len++
    else:
        // 用更小的结尾值优化长度为 pos+1 的状态
        tail[pos] = x

answer = len

lower_bound 就是“第一个 >= x 的位置”，可以用二分实现，时间 O(log len)，而 len <= n。leetcode​

3.5 C 代码实现（O(nlogn)）

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int *tail = (int *)malloc(sizeof(int) * numsSize);
    int len = 0;  // 当前已知的 LIS 长度

    for (int i = 0; i < numsSize; ++i) {
        int x = nums[i];

        // 在 tail[0..len) 中找第一个 >= x 的位置
        int left = 0, right = len;  // 区间是 [left, right)
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tail[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // left 即为 lower_bound 位置
        tail[left] = x;

        // 如果 x 放在了当前最长序列的后面，长度 +1
        if (left == len) {
            len++;
        }
    }

    free(tail);
    return len;
}

每个元素做一次 O(log n) 的二分，整体时间复杂度 O(n log n)。
只用了一个长度为 n 的辅助数组 tail，空间复杂度 O(n)。leetcode​

---

4. 两种方法对比总结

维度	O(n²) DP	O(nlogn) 二分 + tail
核心状态	dp[i]：以 i 结尾的 LIS 长度 leetcode​	tail[k]：长度为 k+1 的 LIS 的最小结尾 leetcode​
转移方式	双层循环枚举 j < i leetcode​	对每个 nums[i] 在 tail 中二分找位置 leetcode​
能否恢复序列	可以（记录前驱即可）leetcode​	只求长度简单，若要恢复需另加结构 leetcode​
时间复杂度	O(n²) leetcode​	O(nlogn) leetcode​
实现难度	思路直观，适合入门 DP leetcode​	思想更抽象些，但代码长度不大 leetcode​

---

如果你想把这篇博客再扩展，可以加一节“如何从 O(n²) 自然想到 O(nlogn)（用‘最优状态’压缩 DP）”，或者加一段“打印 tail 每一步变化”的调试代码，帮助读者直观理解。

https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150