最长上升子序列问题的算法优化

发表于 2025-02-12 分类于信息学阅读次数： 41 Valine：

记录一种将LIS问题的算法优化成 $O (n \log n)$ 的方法。

之前我熟知的dp方法，即定义 $d p (i)$ 为以 $a_{i}$ 结尾的LIS的长度，虽然好想，但复杂度是 $O (n^{2})$ 。

不妨使用一种新的定义方法：记 $d p (i)$ 表示所有长度为 $i$ 的 LIS 中结尾的最小值，若不存在值为 INF 。

我们从 $1$ 到 $n$ 依次枚举 $a_{j}$ 来更新 dp 值，如果存在 $j$ 使得 $a_{j} > d p (i - 1)$ ，考虑到我们是从左往右遍历dp数组的，此时的 $a_{j}$ 肯定是在 $d p (i - 1)$ 这个值在数组 $a$ 中对应的位置的右侧，因此可以接到 $d p (i - 1)$ 所对应的LIS的末尾。那么，我们可以使用 $d p (i) = min {d p (i), a_{j}}$ 来更新 dp 数组了，换而言之，当 $d p (i) > a_{j}$ 时， dp 被更新。

于是，现在我们的任务就变成，找到一个 $i$ ，使得 $d p (i - 1) < a_{j} < d p (i)$ 。这显然非常适合用 lower_bound 来找。下面我们只需要证明dp数组是递增的。

假设 dp 并非递增，则存在 $i$ 使得 $d p (i) > d p (i + 1)$ ，此时，若将 $d p (i)$ 所对应的 LIS 的最后一位替换成 $d p (i + 1)$ ，就构造出了一个末尾更小的长度为 $i$ 的 LIS ，与 $d p (i)$ 的定义相矛盾。

于是对于每个 $a_{j}$ 我们都可以使用二分法在 dp 数组中找到其对应的 $i$ 。最后，答案即使得 $d p (i)$ < INF成立的最大的 $i$ 。

代码：

int solve() {
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++) {
        *lower_bound(dp + 1, dp + n + 1, a[i]) = a[i];
    }
    return lower_bound(dp + 1, dp + n + 1, 0x3f3f3f3f) - dp - 1;
}