题目描述

给定一个序列，求其最长上升子序列长度，要求在 $O(nlogn)$ 的时间复杂度以内完成。

算法

记录一下这一道经典题。

首先，用动态规划做最长上升子序列是 $O(n^2)$ 的，对于每一个数，前面所有比它小的数都可以和它组成一个上升子序列，或者它单独是一个子序列，取最大值即可。

但是，这个算法仍有不足之处。例如样例：3 1 2 1 8 5 6 中，遍历到第二个数时，其实可以不考虑第一个数 $3$ 了。因为 $3$ 后面无论接上什么数，这些数都可以接到 $1$ 上。而 $1$ 后面除了 $3$ 能接的数外，还可以接 $1$ 和 $3$ 中间的数（2,3），所以将 $3$ 替换成 $1$ 一定不劣。

这就启发我们，对于所有长度相同的上升子序列中，我们可以只保留最后一个数最小的那一个子序列，因为最后一个数较大的情况下能接上去的数一个能接到较小的数上，而较小的数能接上的不一定较大的也能。

假设最长上升子序列的长度为 $l$，那么所有的上升子序列就被分成了 $l$ 类，即长度为 $1,2,3,…,l$ 的上升子序列。假设第 $i$ 类的所有上升子序列的最后一个数最小的那一个上升子序列的最后一个数为 $q_i$。

$q$ 数组有什么性质呢？它是单调递增的，因为 $q$ 的第 $i$ 位一定是接一个比它小的数才能构成 $q$ 的第 $i + 1$ 位，那就说明 $q_i < q_{i + 1}$。或者从另一个角度，用反证法，假如存在一个 $q_i > q_{i + 1}$，而 $q_{i + 1}$ 一定对应了一个上升子序列，我们也一定可以找出它。那么这个上升子序列的前 $i - 1$ 为也一定是一个上升子序列，且这个数小于 $q_{i + 1}$ 也小于 $q_i$，这就与 $q_i$ 是所有长度为 $i$ 的上升子序列的最后一个数最小的那个上升子序列的最后一个数相矛盾。

好的，对于每一个 $a_i$ 而言，我们都要考虑将它接到哪个上升子序列里带来的收益最大。显然我们只能将它接到最后一个数小于它自己的那些上升子序列里，而且接到大一些的数里一定比接到小一些的数里更划算，因为那些小一些的数还可以接其他的、比这个数更小的数里面。所以我们要求的实际上就是小于这个数的最大值，直接二分即可。

然后是统计答案。就用能接到的最优的那个上升子序列的长度加一更新最长长度 $l$，然后更新 $q$ 即可。

时间复杂度 $O(nlogn)$。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, inf = 2e9;

int n, a[N], q[N], len;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    q[0] = -inf;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    cout << len << endl;
    return 0;
}