最长递增子序列（LIS）如何求？O(n²) 和 O(n log n) 两种解法

简化版

最长递增子序列（LIS）：从数组里删掉一些元素（不改变剩余顺序），得到的严格递增序列最长有多长。子序列可以不连续（区别于子数组）。O(n²) 的 DP：dp[i] = 以 nums[i] 结尾的 LIS 长度，dp[i] = max(dp[j]) + 1（所有 j<i 且 nums[j]<nums[i]），答案是 max(dp[i])。更优的 O(n log n) 用「贪心 + 二分」维护一个 tails 数组。

详细版

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

int lengthOfLIS(int[] nums) {
    int n = nums.length, ans = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);              // 每个元素自成长度 1 的子序列
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i])   // 能接在 nums[j] 后面
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        ans = Math.max(ans, dp[i]);  // 答案是所有 dp[i] 的最大值
    }
    return ans;
}

解法二：O(n log n) 贪心 + 二分

int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();   // tails[k]=长度 k+1 的递增子序列的最小末尾
    for (int x : nums) {
        int i = lowerBound(tails, x);          // 找第一个 >= x 的位置
        if (i == tails.size()) tails.add(x);   // x 比所有末尾都大，接到最后，LIS 变长
        else tails.set(i, x);                  // 否则替换，让该长度的末尾更小
    }
    return tails.size();
}

DP 的状态是「以 i 结尾」，所以答案要取 max(dp[i])，不是 dp[n-1]。
二分解法的 tails 长度就是 LIS 长度，但 tails 内容不一定是真正的 LIS。

完整版教学

一、问题：最长递增子序列（子序列 ≠ 子数组）

LIS：nums = [10,9,2,5,3,7,101,18]，最长递增子序列是 [2,3,7,18] 或 [2,3,7,101]，长度 4。

必须分清两个概念：

子序列（subsequence）：删掉若干元素、保持剩余相对顺序，元素可以不连续。LIS 求的是子序列。
子数组 / 子串（subarray）：必须连续的一段。

这题求的是子序列，所以 2 和 5 之间隔着别的数也能一起入选。

二、O(n²) DP：以 i 结尾的 LIS

定义状态：dp[i] = 「以 nums[i] 结尾的最长递增子序列长度」。注意「以 i 结尾」这个限定很重要——它保证了无后效性，也让转移能落地。

为什么必须是「以 i 结尾」？如果状态定义成「前 i 个元素的 LIS 长度」，那么在考虑第 i+1 个元素时，我们不知道前面那个 LIS 的末尾是多少，没法判断 nums[i+1] 能不能接上去。而「以 i 结尾」明确了末尾就是 nums[i]，转移才有依据。

三、转移方程与答案

对每个 i，往前看所有 j < i：如果 nums[j] < nums[i]，说明 nums[i] 可以接在「以 j 结尾的 LIS」后面，长度变成 dp[j] + 1。在所有能接的 j 里取最大：

dp[i] = max( dp[j] + 1 )   对所有 j < i 且 nums[j] < nums[i]

若前面没有比 nums[i] 小的，dp[i] 就是 1（自己单独成序列）。

关键易错点：最终答案是 max(dp[i])，不是 dp[n-1]。 因为 LIS 可能不以最后一个元素结尾。很多人惯性地返回 dp[n-1] 而错。

两层循环，时间 O(n²)、空间 O(n)。

四、O(n log n)：贪心 + 二分（tails 数组）

要更快，用一个巧妙的贪心：维护数组 tails，tails[k] 表示「长度为 k+1 的所有递增子序列中，最小的那个末尾值」。核心直觉是——同样长度的递增子序列，末尾越小，越有利于后面接更多元素。

遍历每个 x：

在 tails 里二分找第一个 >= x 的位置 i（lowerBound）；
若没找到（x 比 tails 所有元素都大）：x 能接在最长序列后面，tails.add(x)，LIS 长度 +1；
若找到位置 i：用 x 替换 tails[i]——因为 x 能让「长度 i+1 的子序列」的末尾变得更小（或相等），为后续留更多空间。

遍历完，tails 的长度就是 LIS 的长度。因为每个元素做一次二分，总复杂度 O(n log n)。

五、为什么 tails 能二分；严格 vs 非严格

tails 一定是严格递增的（长度越长、最小末尾越大），所以能用二分。这是它成立的前提。
tails 的长度对，但内容不一定是真正的 LIS——它只是「各长度的最小末尾」拼出来的，可能不是数组里真实存在的一条子序列。想还原真正的 LIS，需要额外记录前驱。面试若只问长度，二分法足够；问具体序列，用 O(n²) DP 加回溯更直接。
严格递增用 lowerBound（第一个 >= x）；若题目要求非严格递增（允许相等），改成 upperBound（第一个 > x）即可。这个细节常被追问。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：O(n²) 中 dp[i] 是以 i 结尾的 LIS；O(n log n) 中 tails[len-1] 是长度 len 的递增子序列可取得的最小尾值。

转移过程是：DP 枚举 j<i 且 a[j]<a[i]；tails 对严格递增使用 lower_bound 找第一个 ≥x 的位置替换。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：[10,9,2,5,3,7,101,18] 的 tails 演化到 [2,3,7,18]，长度 4，但 tails 本身不一定是一条原序列子序列。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：严格递增与非递减分别用 lower_bound/upper_bound；只求长度可用 tails，恢复序列需记录前驱与位置。

核对项	本题答案
复杂度	基础 DP O(n²)/O(n)，tails O(n log n)/O(n)
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：tails 数组就是最终 LIS。 它保存各长度最小尾值，元素可能来自不兼容时刻。
误区：严格递增应替换第一个 >x。 应替换第一个 ≥x；>x 对应非递减版本。
误区：贪心替换会丢掉最优答案。 更小尾值只增加未来接续可能，不会缩短已有长度。
追问：为什么 tails 有序？ 长度更长的递增序列尾值必大于其更短前缀尾值。
追问：如何恢复 LIS？ 记录每个元素的前驱和它更新的 tails 位置。
追问：n 较小时选哪种？ O(n²) 状态直观且易扩展计数，约束大时选二分优化。

九、加强记忆

LIS 求最长严格递增子序列（可不连续）。O(n²) DP：dp[i] = 以 i 结尾的 LIS 长度，dp[i]=max(dp[j]+1)（j<i 且 nums[j]<nums[i]），答案取 max(dp[i]) 而非 dp[n-1]。O(n log n)：贪心 + 二分维护 tails（tails[k]=长度 k+1 子序列的最小末尾），每个数二分找第一个 >= 它的位置替换、比所有大就追加，tails 长度即 LIS 长度（内容不一定是真 LIS）。严格用 lowerBound、非严格用 upperBound。

简化版

详细版