最长上升子序列

给定一个包含 $n$ 个数的数组： $a[0 \dots n-1]$ 。任务是在 $a$ 中找到最长的严格递增子序列。

形式化地说，我们要寻找最长的下标序列 $i_1,\dots,i_k$ ，使得

i_1 < i_2 < \dots < i_k,\quad a[i_1] < a[i_2] < \dots < a[i_k]

本文将讨论解决这一问题的多种算法。此外，我们还会讨论一些可以归约为该问题的其他问题。

使用动态规划的 $O(n^2)$ 解法

动态规划是一种非常通用的技术，可以解决很大一类问题。这里我们将这种技术应用到当前这个具体问题中。

首先，我们只寻找最长递增子序列的长度，之后再学习如何恢复子序列本身。

求长度

为了完成这个任务，我们定义一个数组 $d[0 \dots n-1]$ ，其中 $d[i]$ 表示以索引 $i$ 处的元素结尾的最长递增子序列的长度。

示例

\begin{array}{ll} a &= \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} \\ d &= \{1, 1, 2, 3, 3, 1, 1, 4, 5, 2\} \end{array}

以索引 4 结尾的最长递增子序列是 $\{3,4,5\}$ ，长度为 3；以索引 8 结尾的最长递增子序列可以是 $\{3,4,5,7,9\}$ 或 $\{3,4,6,7,9\}$ ，二者长度都为 5；以索引 9 结尾的最长递增子序列是 $\{0,1\}$ ，长度为 2。

我们将逐步计算这个数组：先计算 $d[0]$ ，然后计算 $d[1]$ ，依此类推。计算完整个数组之后，问题的答案就是数组 $d[]$ 中的最大值。

现在假设当前索引为 $i$ 。也就是说，我们要计算 $d[i]$ ，而之前的所有值 $d[0],\dots,d[i-1]$ 都已经知道。那么有两种情况：

$d[i]=1$ ：所需的子序列只包含元素 $a[i]$ 。
$d[i]>1$ ：子序列将以 $a[i]$ 结尾，而在它之前会有某个数 $a[j]$ ，其中 $j<i$ 且 $a[j]<a[i]$ 。

很容易看出，以 $a[j]$ 结尾的这个子序列本身必然是以 $a[j]$ 结尾的最长递增子序列之一。数 $a[i]$ 只是把这个最长递增子序列再扩展一个数。

因此，我们只需要遍历所有满足 $j<i$ 且 $a[j]<a[i]$ 的 $j$ ，将 $a[i]$ 添加到以 $a[j]$ 结尾的最长递增子序列后面，并从所得序列中取最长的那个。以 $a[j]$ 结尾的最长递增子序列长度为 $d[j]$ ，将其扩展一个元素后，长度就是 $d[j]+1$ 。

d[i]=\max_{\substack{j<i\\a[j]<a[i]}}\left(d[j]+1\right)

如果把这两种情况结合起来，就得到 $d[i]$ 的最终表达式：

d[i]=\max\left(1,\max_{\substack{j<i\\a[j]<a[i]}}\left(d[j]+1\right)\right)

实现

下面是上述算法的一种实现，它计算最长递增子序列的长度。

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

恢复子序列

到目前为止，我们只学会了如何求子序列的长度，还没有学习如何找到子序列本身。

为了能够恢复子序列，我们再生成一个辅助数组 $p[0 \dots n-1]$ ，并在计算数组 $d[]$ 的同时计算它。 $p[i]$ 表示以 $i$ 结尾的最长递增子序列中倒数第二个元素的索引 $j$ 。换句话说，索引 $p[i]$ 就是使 $d[i]$ 取得最大值时对应的那个索引 $j$ 。从某种意义上说，这个辅助数组 $p[]$ 指向各个元素的“祖先”。

然后，为了得到子序列，我们只需要从具有最大 $d[i]$ 的索引 $i$ 开始，沿着这些祖先不断向前，直到得到完整的子序列，也就是说，直到到达满足 $d[i]=1$ 的元素。

恢复过程的实现

我们对前面几节中的代码稍作修改。我们将在计算 $d[]$ 的同时计算数组 $p[]$ ，然后再计算子序列。

为了方便，我们最初令祖先 $p[i]=-1$ 。对于满足 $d[i]=1$ 的元素，它们的祖先值将保持为 $-1$ ，这会使恢复子序列稍微方便一些。

vector<int> lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1), p(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    int ans = d[0], pos = 0;
    for (int i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    vector<int> subseq;
    while (pos != -1) {
        subseq.push_back(a[pos]);
        pos = p[pos];
    }
    reverse(subseq.begin(), subseq.end());
    return subseq;
}

恢复子序列的另一种方法

也可以不使用辅助数组 $p[]$ 来恢复子序列。我们可以简单地重新计算当前的 $d[i]$ 值，同时观察最大值是如何得到的。

这种方法会使代码稍微长一些，但作为回报，我们可以节省一些内存。

使用动态规划和二分查找的 $O(n\log n)$ 解法

为了得到更快的解法，我们构造另一种运行时间为 $O(n^2)$ 的动态规划方法，然后再把它改进为 $O(n\log n)$ 。

我们将使用动态规划数组 $d[0 \dots n]$ 。这一次， $d[l]$ 并不对应元素 $a[i]$ ，也不对应数组的某个前缀。 $d[l]$ 表示长度为 $l$ 的递增子序列能够以其结尾的最小元素。

最初我们假设 $d[0]=-\infty$ ，而对于其他所有长度，都有 $d[l]=\infty$ 。

我们仍然逐个处理这些数，先处理 $a[0]$ ，然后是 $a[1]$ ，依此类推，并在每一步维护数组 $d[]$ ，使它始终保持最新状态。

示例

给定数组 $a=\{8,3,4,6,5,2,0,7,9,1\}$ ，下面列出了它的所有前缀以及对应的动态规划数组。注意，数组中的值并不总是在末尾发生变化。

\begin{array}{ll} \text{prefix}=\{\} &\quad d=\{-\infty,\infty,\dots\}\\ \text{prefix}=\{8\} &\quad d=\{-\infty,8,\infty,\dots\}\\ \text{prefix}=\{8,3\} &\quad d=\{-\infty,3,\infty,\dots\}\\ \text{prefix}=\{8,3,4\} &\quad d=\{-\infty,3,4,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6\} &\quad d=\{-\infty,3,4,6,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6,5\} &\quad d=\{-\infty,3,4,5,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6,5,2\} &\quad d=\{-\infty,2,4,5,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6,5,2,0\} &\quad d=\{-\infty,0,4,5,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6,5,2,0,7\} &\quad d=\{-\infty,0,4,5,7,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6,5,2,0,7,9\} &\quad d=\{-\infty,0,4,5,7,9,\infty,\dots\}\\ \text{prefix}=\{8,3,4,6,5,2,0,7,9,1\} &\quad d=\{-\infty,0,1,5,7,9,\infty,\dots\} \end{array}

当我们处理 $a[i]$ 时，可以问自己：要把当前的数 $a[i]$ 写入数组 $d[0\dots n]$ ，需要满足什么条件？

如果存在一个长度为 $l$ 、以 $a[i]$ 结尾的最长递增序列，并且不存在另一个长度为 $l$ 、以更小的数结尾的最长递增序列，那么我们令 $d[l]=a[i]$ 。与前一种方法类似，如果从长度为 $l$ 的最长递增序列中去掉 $a[i]$ ，就会得到另一个长度为 $l-1$ 的最长递增序列。

因此，我们希望用数 $a[i]$ 去扩展一个长度为 $l-1$ 的最长递增序列。显然，在所有长度为 $l-1$ 的最长递增序列中，以最小元素结尾的那个效果最好，换句话说，就是以元素 $d[l-1]$ 结尾的长度为 $l-1$ 的序列。

当且仅当 $d[l-1]<a[i]$ 时，存在一个长度为 $l-1$ 的最长递增序列，可以用数 $a[i]$ 对它进行扩展。因此，我们可以遍历每一个长度 $l$ ，并通过检查这一条件来判断能否扩展一个长度为 $l-1$ 的最长递增序列。

此外，我们还需要检查是否已经找到一个长度为 $l$ 、且结尾元素更小的最长递增序列。因此，只有当 $a[i]<d[l]$ 时，我们才进行更新。

处理完 $a[]$ 中的所有元素之后，所求子序列的长度就是满足 $d[l]<\infty$ 的最大 $l$ 。

使用 $\pm\infty$ 作为填充值只是为了方便表述递推关系；实际并不需要存储它们。在下面的实现中，我们只保留那些长度已经真正出现过的项。于是， $d[]$ 在每一步最多只会增加一个元素；访问超过它末尾的位置，就对应于原来的 $d[l]=\infty$ ，而答案就是它的大小。

int lis(vector<int> const& a) {
    vector<int> d;
    for (int x : a) {
        size_t l = 0;
        while (l < d.size() && d[l] < x)
            l++;
        if (l == d.size())
            d.push_back(x);
        else
            d[l] = x;
    }
    return d.size();
}

现在我们作出两个重要观察。

数组 $d$ 始终是有序的：对于所有 $l=1\dots n$ ，都有 $d[l-1]<d[l]$ 。

这是显然的，因为只要从长度为 $l$ 的递增子序列中去掉最后一个元素，就会得到一个长度为 $l-1$ 、且结尾元素更小的递增子序列。

元素 $a[i]$ 最多只会更新一个 $d[l]$ 的值。

这一点可以直接从上面的实现中看出。在数组中只可能存在一个位置满足

d[l-1]<a[i]<d[l].

因此，我们可以使用二分查找，在 $O(\log n)$ 的时间内在数组 $d[]$ 中找到这个元素。实际上，我们可以直接在数组 $d[]$ 中寻找第一个大于等于 $a[i]$ 的数，然后按照上面的实现方式尝试更新这个元素。

实现

这样就得到了改进后的 $O(n\log n)$ 实现，它与上面的代码相比，唯一的区别就是寻找位置的方法：

int lis(vector<int> const& a) {
    vector<int> d;
    for (int x : a) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end())
            d.push_back(x);
        else
            *it = x;
    }
    return d.size();
}

恢复子序列

使用这种方法同样可以恢复子序列。一种直接的方法是维护两个辅助数组：一个用于把 $d[]$ 中的每个位置映射回它在 $a[]$ 中的索引，另一个是“祖先”数组 $p[i]$ ，其中保存以 $a[i]$ 结尾的最优子序列中前一个元素的索引。

不过，我们也可以采用一种更节省内存的方法，只使用一个辅助数组 $p[0\dots n-1]$ ，并把它作为算法已经执行的二分查找的副产品记录下来。令 $p[i]$ 表示 $a[i]$ 最终位于 $d[]$ 中的位置，因此，以 $a[i]$ 结尾的最长递增子序列长度为 $p[i]+1$ 。

现在假设 LIS 的长度为 $L$ ，我们从后向前遍历 $a[]$ ，先选择最后一个满足 $p[i]=L-1$ 的元素，再选择它之前最后一个满足 $p[i]=L-2$ 的元素，依此类推，直到 $p[i]=0$ 。按照这种方式选出的每个元素，都是前一个已选元素的合法前驱。事实上，假设我们已经选择了满足 $p[j]=l+1$ 的 $a[j]$ ，并令 $a[i]$ 为它之前最后一个满足 $p[i]=l$ 的元素。

由于 $d[l]$ 始终保存最近一次被放到位置 $l$ 的元素，因此在处理 $a[j]$ 的那一刻，它等于 $a[i]$ 。而二分查找之所以把 $a[j]$ 放到位置 $l+1$ ，正是因为 $d[l]<a[j]$ ，因此 $a[i]<a[j]$ 。

按照这种方式收集元素，并在最后将它们反转，就可以得到一个最长递增子序列。

vector<int> lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d, p(n);

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(d.begin(), d.end(), a[i]);
        p[i] = it - d.begin();
        if (it == d.end())
            d.push_back(a[i]);
        else
            *it = a[i];
    }

    int l = d.size() - 1;
    vector<int> subseq;
    for (int i = n - 1; i >= 0 && l >= 0; i--) {
        if (p[i] == l) {
            subseq.push_back(a[i]);
            l--;
        }
    }
    reverse(subseq.begin(), subseq.end());
    return subseq;
}

使用数据结构的 $O(n\log n)$ 解法

除了上面这种在 $O(n\log n)$ 时间内计算最长递增子序列的方法之外，我们也可以采用另一种方法解决这个问题：使用一些简单的数据结构。

回到第一种方法。回忆一下， $d[i]$ 是满足 $j<i$ 且 $a[j]<a[i]$ 的 $d[j]+1$ 。

因此，如果我们再定义一个数组 $t[]$ ，使得

t[a[i]]=d[i],

那么计算 $d[i]$ 的问题，就等价于求数组 $t[]$ 某个前缀中的最大值：

d[i]=\max\left(t[0\dots a[i]-1]+1\right)

求一个会发生变化的数组的前缀最大值，是一个标准问题，可以使用多种不同的数据结构来解决。例如，我们可以使用线段树或树状数组。

这种方法显然存在一些缺点：从实现的长度和复杂度来看，这种方法会比使用二分查找的方法更差。此外，如果输入的数 $a[i]$ 特别大，那么我们就需要使用一些技巧，例如对这些数进行压缩（也就是将它们重新编号为 $0$ 到 $n-1$ ），或者使用动态线段树（只生成树中重要的分支）。否则，内存消耗会过高。

另一方面，这种方法也有一些优点：使用这种方法时，你不需要考虑动态规划解法中的那些微妙性质。而且，这种方法使我们能够非常容易地将问题推广到更一般的情况（见下文）。

练习题

ACMSGURU - “North-East”
Codeforces - LCIS
Codeforces - Tourist
SPOJ - DOSA
SPOJ - HMLIS
SPOJ - ONEXLIS
SPOJ - SUPPER
Topcoder - AutoMarket
Topcoder - BridgeArrangement
Topcoder - IntegerSequence
UVA - Back To Edit Distance
UVA - Happy Birthday
UVA - Tiling Up Blocks

最长上升子序列

使用动态规划的 $O(n^2)$ 解法

求长度

实现

恢复子序列

恢复过程的实现

恢复子序列的另一种方法

使用动态规划和二分查找的 $O(n\log n)$ 解法

实现

恢复子序列

使用数据结构的 $O(n\log n)$ 解法

相关问题

最长不下降子序列

最长递增子序列的数量

覆盖一个序列所需的最少非递增子序列数量

练习题

使用动态规划的 O(n2)O(n^2)O(n2) 解法​

求长度​

实现​

恢复子序列​

恢复过程的实现​

恢复子序列的另一种方法​

使用动态规划和二分查找的 O(nlog⁡n)O(n\log n)O(nlogn) 解法​

实现​

恢复子序列​

使用数据结构的 O(nlog⁡n)O(n\log n)O(nlogn) 解法​

相关问题​

最长不下降子序列​

最长递增子序列的数量​

覆盖一个序列所需的最少非递增子序列数量​

练习题​

使用动态规划的 $O(n^2)$ 解法

求长度

实现

恢复子序列

恢复过程的实现

恢复子序列的另一种方法

使用动态规划和二分查找的 $O(n\log n)$ 解法

实现

恢复子序列

使用数据结构的 $O(n\log n)$ 解法

相关问题

最长不下降子序列

最长递增子序列的数量

覆盖一个序列所需的最少非递增子序列数量

练习题