C++怎么实现最长递增子序列-C++-PHP中文网

std::lower_bound可实现O(n log n)严格递增LIS长度计算，维护最小末尾数组并二分替换首个≥当前数位置，避免upper_bound导致重复元素误入；输入{10,9,2,5,3,7,101,18}得长度4。

c++怎么实现最长递增子序列

用 `std::lower_bound` 实现 O(n log n) 的 LIS 长度计算

直接求最长递增子序列（LIS）长度，不用还原具体序列时，std::lower_bound 是最实用的选择。它维护一个「可能的最小末尾数组」，每次用二分替换掉第一个 ≥ 当前数的位置，保证数组始终单调递增且尽可能“紧凑”。

常见错误是误用 std::upper_bound —— 它会导致重复元素被错误接纳，破坏严格递增语义；严格递增必须用 lower_bound。

输入数组为 nums = {10, 9, 2, 5, 3, 7, 101, 18}，最终维护的辅助数组可能是 {2, 3, 7, 18}（长度 4），但该数组不一定是真实子序列，仅长度准确
时间复杂度稳定 O(n log n)，空间 O(n)；比暴力 DP 的 O(n²) 快得多，尤其适合 n > 1e4 的场景
注意：该方法只适用于「严格递增」（a[i] ）。若需「非递减」（允许相等），应改用 upper_bound

vector<int> tails;
for (int x : nums) {
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
}
return tails.size();
</int>

还原具体的 LIS 路径需要额外记录 `parent` 和 `index`

只算长度容易，但面试或调试时常需返回任意一个最长递增子序列（比如 {2, 3, 7, 18}）。这时不能只靠 tails 数组，必须在构建过程中同步记录每个位置的前驱索引。

关键点在于：每次更新 tails 中某个位置时，要记下「谁导致了这次更新」——即当前元素在原数组中的下标，以及它接在哪个已有元素之后。

声明两个辅助数组：prev[i] 表示 nums[i] 在 LIS 中的前一个元素下标，初始为 -1；tail_indices[k] 记录长度为 k+1 的 LIS 的末尾元素在 nums 中的下标
每次调用 lower_bound 得到插入位置 pos 后，若 pos > 0，则 prev[i] = tail_indices[pos-1]
最后从 tail_indices.back() 开始，沿 prev 链表反向构造结果（记得 reverse）