最长上升子序列 (LIS, Longest Increasing Subsequence)：在给定序列中找到最长的子序列，满足子序列升序。

模板题：Acwing 895

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 $N$。

第二行包含 $N$ 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

$1\le N\le 1000$
$-{10}^9\le \mathrm{数}\mathrm{列}\mathrm{中}\mathrm{的}\mathrm{数}\le {10}^9$

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

$O(n^2)$ 解法：动态规划

流程和思路

$a_i:=$ 序列中的第 $i$ 个数（下标从 $1$ 开始）

$dp(i):=$ 以 $a_i$ 为结尾的子序列的最大长度

由于我们要求子序列严格单调上升，那么如果 $j<i$ 且 $a_j<a_i$，下一个元素 $a_i$ 就可以接到 $a_j$ 的后面，那么 $dp(i)=dp(j)+1$.

为了让子序列最长，我们遍历 $[1,i)$，取最大值即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1010;
int N, a[MAXN];
int dp[MAXN];

int main()
{
    a[0] = INT32_MIN;
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> a[i];
    for (int i = 1; i <= N; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    int ans = 0;
    for (int i = 1; i <= N; i++)
        ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}

$O(n\log n)$ 解法：贪心、二分、单调栈

单调栈：https://io.zouht.com/6.html

流程

使用一个数组 $v$ 作为单调递增栈，遍历 $a_1\sim a_n$，对于每个 $a_i$：

• 若 $a_i>v_{top}$，则将 $a_i$ 入栈。
• 若 $a_i\le v_{top}$，则用 $a_i$ 替换掉 $v$ 中第一个 $\ge a_i$ 的数。

遍历完成整个序列后，$v$ 的长度即为最长上升子序列的长度。

思路

这种方法有一点理解难度，先用一个例子进行模拟：

$a=[3,1,4,1,5,9,2]$

循环过程中 $v$ 的变化：

1. $v=[3]$
2. $v=[1]$
3. $v=[1,4]$
4. $v=[1,4]$
5. $v=[1,4,5]$
6. $v=[1,4,5,9]$
7. $v=[1,2,5,9]$

最终，$v$ 的长度为 $4$ 即最长上升子序列长度。

我们会发现一些奇怪之处：

• 这个单调栈的去尾操作并不典型，$6\sim 7$ 步时，数字 $9$ 没有被去除而是保留下来了。
• 单调栈的序列并不是最长上升子序列，该例应该为 $[1,4,5,9]$ 而不是 $[1,2,5,9]$

---

首先解决第一个问题，为什么用这种特殊的去尾操作？

原因是贪心，我们要求的是最长的上升子序列，当然不愿意越算子序列长度反而越小了。因此，如果我们目前算出的结果还没以前的长，会暂时保留以前的结果，当然也不丢弃目前的结果，因为之后继续计算的话，目前的结果可能更优。

为了实现上述目的，我们可以用新序列从左到右逐渐覆盖掉旧序列。当新序列长度 $<$ 原序列长度时，原序列没有被完全覆盖，因此保证长度不减小；当新序列长度 $\ge$ 原序列长度时，原序列已经被完全覆盖，现在就是以新序列为基础进行计算了。

因此就产生了这种特别的去尾方式。上述例子的第 $7$ 步可以表示成：

$$\begin{array}{rl}\mathrm{之}\mathrm{前}\mathrm{的}\mathrm{更}\mathrm{好}\mathrm{的}\mathrm{序}\mathrm{列}:v=& [1,4,5,9]\\ \mathrm{现}\mathrm{在}\mathrm{的}\mathrm{新}\mathrm{序}\mathrm{列}:v=& [1,2]\\ \mathrm{覆}\mathrm{盖}\mathrm{储}\mathrm{存}:v=& [1,2,5,9]\end{array}$$

---

第一个问题解决后，第二个问题其实就比较容易了，因为栈中储存的不只有一个序列，是以前的序列和现在的序列合并的产物，因此不一定是最终最长上升子序列。

但是对于长度，由于我们的贪心思想，我们循环过程中栈的长度不减，因此能够保证最长上升子序列的长度就是栈的长度。

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
int N, a[MAXN];
vector<int> v;

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> a[i];
    v.push_back(a[1]);
    for (int i = 2; i <= N; i++)
    {
        if (a[i] > v.back())
            v.push_back(a[i]);
        else
            v[lower_bound(v.begin(), v.end(), a[i]) - v.begin()] = a[i];
    }
    cout << v.size() << endl;
    return 0;
}