LIS模型

一、问题原型

给定序列 $a_1,a_2,\dots,a_n$，选择一组下标 $i_1<i_2<\cdots<i_k$，并要求 $a_{i_1}<a_{i_2}<\cdots<a_{i_k}$。

目标是最大化所选元素数量 $k$，这个最大值称为最长严格上升子序列长度，即 LIS。

最长上升子序列 LIS ：Longest Increasing Subsequence
最长不下降子序列 LNDS ：Longest Non-Decreasing Subsequence

LIS 同时要求下标递增与元素值递增。也可以理解为：在原序列中删除一部分元素，使剩余元素严格递增，并让保留元素尽可能多。

子序列与子数组

子序列不要求连续，而子数组要求连续。若问题要求连续区间，一般不属于 LIS 模型。

---

二、为什么状态要按结尾定义

首先尝试一种最自然的定义：$f_{i}$ 表示前 $i$ 个元素的 LIS 长度。处理新元素 $a_i$ 时，我们希望由 $f_{i-1}$ 推出 $f_i$。

问题在于，因为我们只知道此前的最长长度，并不知道对应子序列以什么值结尾，也就无法判断 $a_i$ 能否接在它后面。

因此，必须把结尾信息放入状态：$f_{i}$ 表示以 $a_{i}$ 为结尾的严格上升子序列长度。

若 $a_{i}$ 接在 $a_{j}$ 后面，必须满足 $j < i$ 且 $a_{j} < a_{i}$，那么转移就是 $\displaystyle f_{i} = 1 + \max_{j < i, a_{j} < a_{i}}(f_{j})$。若不存在合法的 $j$，则 $f_{i} = 1$，最终答案为 $\displaystyle \max_{1 \le i \le n}(f_{i})$。

任意一条以 $a_i$ 结尾的上升子序列，删去最后一个元素后，都落入某个合法前驱状态；任意合法前驱接上 $a_i$，也都会形成合法方案。

因此，这个转移恰好覆盖了所有以 $a_{i}$ 结尾的合法方案。

---

三、朴素 DP 的瓶颈

接着我们分析复杂度，由于每个位置 $i$ 都要枚举此前所有位置 $j$，所以时间复杂度为 $\mathcal{O}(N^{2})$。

对于上述定义来说，我们的瓶颈可以表述为：对每个 $a_{i}$，查询此前满足 $a_{j} < a_{i}$ 的状态中最大的 $f_{j}$。

围绕这一查询，可以得到两条不同的优化路线：

1. 保持状态定义不变，使用树状数组或线段树维护值域前缀最大值；
2. 重新组织状态，只保留对未来有用的信息。

前者更接近一般的 [[数据结构优化DP]]，并且具有较强的可推广性；后者则是利用了 LIS 问题特有的最优结尾性质，我们重点讨论法二。

但状态的优劣不再只由长度和结尾决定时，通常保留原 DP 状态，并使用树状数组或线段树维护值域前缀最大值。典型问题参见 LIS题型整理。

---

四、状态支配

核心性质

考虑两条长度相同的严格上升子序列，它们的结尾分别为 $x$ 和 $y$，且 $x \le y$。

若未来元素 $z$ 能接在 $y$ 后面，则 $y<z$，因此也有 $x<z$。所以，所有能扩展结尾 $y$ 的元素，也一定能扩展结尾 $x$。

因此，在长度相同的前提下，结尾越小，未来扩展能力越强。只保留最小结尾，不会损失得到更长答案的可能性。

状态支配

当前完成度相同，而一个状态对所有未来转移都不劣于另一个状态时，劣势状态可以被删除。

最小结尾数组

处理完当前前缀后，定义 $g_k$ 表示长度为 $k+1$ 的严格上升子序列的最小可能结尾。

这里下标从 $0$ 开始，以适配 vector。

数组 g 是严格递增的。因为一条长度为 $k+2$ 的上升子序列，删去最后一个元素后，会得到一条长度为 $k+1$、结尾更小的上升子序列，所以 $g_{k} < g_{k+1}$。

因此，可以在 g 上二分。

如何处理新元素

设当前元素为 $x$，在 g 中找到第一个满足 $g_{k} \ge x$ 的位置，也就是使用 lower_bound。

由于 $k$ 是第一个满足条件的位置，若 $k>0$，则 $g_{k-1}<x$。

所以，$x$ 可以接在长度为 $k$ 的方案后面，形成长度为 $k+1$ 的方案；若 $k=0$，则单独选择 $x$。

另一方面，$g_k$ 已经是长度为 $k+1$ 的方案中的最小结尾，并且 $g_k\ge x$，因此不存在长度为 $k+1$、结尾小于 $x$ 的方案。于是，$x$ 不能形成更长的上升子序列。

所以，我们可以将 $x$ 赋值给 $g_{k}$。( 这就是状态支配 )

若不存在满足 $g_k\ge x$ 的位置，说明 $x$ 可以接在当前最长方案后面，直接加入 g 末尾。

最终，g 数组的长度就是 LIS 长度。

笔记

g 中不同位置的值可能来自不同的历史方案，因此 g 本身不一定是原序列的一条子序列。

复杂度与严格性

每个元素只需在 g 上二分一次，因此：

• 时间复杂度为 $\mathcal{O}(N\log N)$；
• 空间复杂度为 $\mathcal{O}(N)$。

严格上升要求前驱满足 $y<x$，因此替换第一个 $y\ge x$ 的位置，使用 lower_bound。

不下降要求前驱满足 $y\le x$，因此替换第一个 $y>x$ 的位置，使用 upper_bound。

如果要求下降版本的话，可以对所有元素取相反数后转化为上升版本解决。

最小结尾还能提供什么

最小结尾数组不仅能够通过 g.size() 给出全局 LIS 长度。

处理位置 $i$ 的元素 $a_i$ 时，若 lower_bound 返回的位置为 $k$，说明 $a_i$ 能够形成的最长上升子序列长度恰好为 $k+1$。因此，可以在扫描过程中记录：$f_i = k + 1$，其中 $f_i$ 表示以 $a_i$ 结尾的 LIS 长度。

另一方面，处理完某个前缀后，g[k] 表示长度为 $k+1$ 的上升子序列的最小结尾。因此，在结尾不能超过 $X$ 的限制下，能够达到的最大长度就是 g 中不超过 $X$ 的元素数量，可以通过下方代码得到。

upper_bound( g.begin( ), g.end( ), X ) - g.begin( )

前者用于记录每个位置的局部状态，后者用于回答带结尾值域限制的 LIS 查询。

信息边界

最小结尾数组保留：

• 每个长度是否可达；
• 每个长度下最有扩展能力的结尾；
• 当前 LIS 长度。

它舍弃：

• 同长度的其他方案；
• 方案数量；
• 完整前驱关系；
• 未被额外记录的每个位置状态；
• 每条方案的附加权值。

因此，最小结尾可以直接求 LIS 长度，也可以在扫描过程中额外记录每个位置的结尾长度；但它不能直接求方案数、最大权值上升子序列，也不能在存在颜色、次数、差值等额外连接条件时直接套用。

若要恢复一条 LIS，需要额外记录前驱和各长度对应的实际结尾位置。

---

五、知识体系中的位置

1. 线性 DP 中的子序列模型。LIS 是“以结尾划分方案”的典型例子。

2. DAG 最长路。若在满足 $i<j$ 且 $a_i<a_j$ 时连边 $i\to j$，那么 LIS 就是这张 DAG 上的最多节点数的路径。

3. 偏序最长链。将位置表示为二维点 $(i,a_i)$，LIS 就是偏序关系 $(i,a_i)\prec(j,a_j) \iff i<j,\ a_i<a_j$ 下的最长链。

4. 状态支配。$\mathcal{O}(N\log N)$ 做法体现了“同完成度下删除未来扩展能力更差的状态”。

具体的识别、转化与变体参见 LIS题型整理。

---

六、代码实现

▶

LIS

int a[maxn], f[maxn];

// O(N^2)，f[i] 表示以 a[i] 结尾的 LIS 长度
int solve_n2( int N ) {
    int res = 0;
    for( int i = 1; i <= N; ++ i ) {
        f[i] = 1;
        for( int j = 1; j < i; ++ j )
            if( a[j] < a[i] ) f[i] = max( f[i], f[j] + 1 );
        res = max( res, f[i] );
    }
    return res;
}

// O(N logN)，严格上升用 lower_bound；不下降改 upper_bound
int solve_log( vector<int> &arr ) {
    vector<int> g;
    for( int x : arr ) {
        auto it = lower_bound( g.begin( ), g.end( ), x );
        if( it == g.end( ) ) g.push_back( x );
        else *it = x;
    }
    return (int)g.size( );
}