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

发表于 分类于 阅读次数： 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;
}