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

发表于 分类于 阅读次数： Valine：

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

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

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

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

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

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

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

代码：

1
2
3
4
5
6
7
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;
}