最长上长子序列

[[TOC]]

题目

TODO

7
1 7 3 5 9 4 8

一句话算法

每个元素都尝试拼接到它前面的所有元素的后面

题目

TODO

本题是建立在序列上一个题目.

什么是序列?

根据序列 - 维基百科，自由的百科全书的定义，序列定义在集合上的一个函数 $f:\mathbb{N} \rightarrow S$ ，而函数是定义在集合上的一种特殊二元关系。可以直观的把序列理解成排成一列的数。

暴力想法

根据前面所学的集合的知识，设集合为 $S = \{a_1,a_2,\cdots,a_n\}$ ,设问题:在集合 $S$ 上的 $Lis$ 的值,表示为 $f(S)$ ,

设序列 $Q = a_1,a_2,\cdots,a_n$ ,表示原序列.

设 $Q$ 的子序列表示为 $q_i$

那么 $q_i$ 具体是什么呢?

设 $Q = 1,2,3$ 时,那么,如下的列表

\begin{array}{cccc} i & bin(i) & \text{subsequec} \\ \hline \\ p_0 & 000 & \varnothing \\ p_1 & 001 & 1 \\ p_2 & 010 & 2\\ p_3 & 011 & 1,2\\ p_4 & 100 & 3 \\ p_5 & 101 & 1,3\\ p_6 & 110 & 2,3\\ p_7 & 111 & 1,2,3\\ \end{array}

于是得知子序列 $p_i$ 里的元素与下标 $i$ 对应的二进制 $bin(i)$ 有关:

如果 $bin(i)$ 第 $j$ 位为 $0$ ,表示子序列 $p_i$ 不含有 $a_{j+1}$
如果 $bin(i)$ 第 $j$ 位为 $1$ ,表示子序列 $p_i$ 含有 $a_{j+1}$

数学表示为

p_i = [a_j \mid i \& (1\ll(j-1)) = 1]

设 $P$ 表示子序列 $p_i$ 组成的集合 $P = \{p_0,p_1,\cdots p_{2^n}\}$ ,n表示 $Q$ 的元素的个数

序列是定义在集合上的一个函数

函数是一种特殊的二元关系

显然答案是

ans = max\{ len(p) \mid p \in P \land isLis(p) \} \tag 1

根据上面的式子 $(1)$ 写出一个暴力求子集然后判断是否是Lis的代码,即可.

也就是集合 $S$ 的所有子集 $x$ 组合的集合 $P(S) = \{x | x \subseteq S\}$ , $P(S)$ 叫做集合 $S$ 的幂集.

显然集合 $x$ 是有对子集 $x$ 进行编码,

说了那么多,其实使用的算法很简单,就是[ Rbook: 01序列]

点击

//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2024-06-15 15:22:19
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;

int a[maxn];
int b[maxn]; //桶
//记录答案
int ans;

bool is_lis() {
    //前一个数
    int pre = -9999999;
    for(int i =1;i<=n;i++) {
        if( b[i] == 1) {
            if( a[i] < pre)
                return false;
            pre = a[i];
        }
    }
    return true;
}

void print_seq() {
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        if( b[i]) cout << a[i] << " ";
    }
    std::cout << "\n";
}

void dfs(int dep) {
    if( dep > n) {
        int cnt = 0;
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            cnt += b[i];
        }
        if( cnt > ans && is_lis())
        {
            ans = cnt;
            //调试用,输出这个序列
            // print_seq();
        }
        return;
    }
    for(int i = 0;i <= 1 ;++i ) // i: 0->1
    {
        b[dep] = i;
        dfs(dep+1);
    }
}

int main () {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        cin >> a[i];
    }
    dfs(1);
    std::cout << ans << "\n";
    return 0;
}

小朋友法

原问题,设序列为 $S$ ,求序列 $S$ 上的 $LIS$ 的值,表示 $G(S)$

把这个问题转化为 $f(i)$ :第 $i$ 个元素为结尾的 $LIS$ 的值

G(S) = max\{f(1),f(2),\cdots,f(n) \}

这样就转化成了求 $f(i)$ 问题,如何求呢,

显然

f(i) = max\{1,f(j)+1\} \; j < i \land a_j < a_i

于是我们只需要写一个两重循环可以解出答案,时间为 $O(n^2)$

代码

//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2024-06-15 17:45:14
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
int a[maxn];

//f[i] 表示以第i个元素为结尾的最长lis长度
// 边界 f[1] = 1
int f[maxn];
int ans;

int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        cin >> a[i];
    }
    f[1] = 1;

    //从第2个元素开始
    for(int i = 2;i <= n ;++i ) // i: 2->n
    {
        int t = 0;
        for(int j = 1;j < i ;++j ) // j: 1->i
        {
            if( a[j] <= a[i] && t < f[j])
                t = f[j];
        }
        f[i] = t + 1;
    }
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        if( ans < f[i])
            ans = f[i];
    }
    cout << ans;
    
    return 0;
}

时间复杂度为: $O(n^2)$

证明

上面我们通过小朋友法,得到了一个式子如下:

G(S) = max\{f(1),f(2),\cdots,f(n) \}

似乎很突兀,你可能会有两个疑问:

如何证明这个公式是正确的
如何思考可以最终得到这个公式呢?思维的过程是什么.

下面的用集合想法来证明.

设原序列为 $S = a_1, a_2, a_3, a_4, a_5, a_6, a_7$ , $P(7)$ 表示序列 $S$ 的前 $7$ 个元素的所有子集组成的集合,设 $x \in P(7)$

用数字 $n$ 表示一个前n个元素组成的集合是一种常用的集合表示法.

设 $g(x)$ 表示 $x$ 对应的 $lis$ 值,具体如下:

g(x) = \left\{ \begin{aligned} &\vert x \vert & x \text{各个元素是符合Lis的} \\ &0 & \text{如果$x$是空集}\\ \end{aligned} \right.

根据集合分类的思想,考虑是后一个元素,要么包含最后一个元素 $a_7$ ,要么不包含

根据最后一个元素 $a_7$ ,是否包含,把 $P(7)$ 里的元素分成了两类

$P_{a_7}(7)$ ,含有 $a_7$ 的子集集合
$P_{ \bcancel{a_7}}(7)$ ,不含有 $a_7$ 的子集集合

那么需要求前 $7$ 个元素的能得到的最大 $lis$ 值

设 $G(7)$ 表示 $P(7)$ 中符合条件的最长的那个元素的长度

$G_{a_7}(7) = f(7)$ , $P_{a_7}(7)$ ,含有 $a_7$ 的的子集的答案
$G_{ \bcancel{a_7}}(7) = G(6)$ ,针对 $P_{ \bcancel{a_7}}(7)$ ,得到的答案

G(7) = \left\{ \begin{aligned} &G_{a_7}(7) = f(7) \\ &G_{\bcancel{a_7}}(7) = G(6) \\ \end{aligned} \right.

显然 $G(6)$ 还可以继续分解

G(7) = \left\{ \begin{aligned} &G_{a_6}(6) = f(6) \\ &G_{\bcancel{a_6}}(6) = G(5) \\ \end{aligned} \right.

如果按这种方式继续分,可以分成到最后一个式子是

G(1) = \left\{ \begin{aligned} &G_{a_1}(1) = f(1) = 1 \\ &G_{\bcancel{a_1}}(1) = G(0) = 0 \\ \end{aligned} \right.

可以想到,按这方式对集合进行划分,符合不重不漏的原则,且最后所有的问题都可以转成 $f(i)$ ,于是我们成功的把原问题转成了 $max\{\}$

显然 $f(S)$ 分解成了一子问题 $g(S,a_n)$ 与原问题不相似,连参数都不一样,这不一种好的分解子问题的方式,或集合分类方式.但这启发了我们.

为了方法,我们用数字来表示集合,如 $4$ ,就是表示前 $4$ 个元素表示的集合 $\{a_1,a_2,a_3,a_4\}$

显然,可以用 $g(n,a_n)$ 来表示前 $n$ 个元素组成的集合,且一定含有的 $a_n$ 最为最后一个元素的 $lis$ 的值

那么

g(n,a_n) = max(\{g(i,a_i) \big\vert i \leqslant n \land a_i \leqslant a_n \}) +1

$g(n,a_n)$ 的答案,就是符合条件的子集合组成的集合的最值加 $1$ ,成功建立起和子集合之间的关联

f(S) = max(\{g(i,a_i) \big\vert i \in [1,n]\})

建立起了最终问题与 $g$ 的关联.

思考

本质上可以把这个题目看成一个竖着的单列数字金字塔,只不过从点 $i$ 到达某个点 $j$ 是有条件的.

延伸:最少递增子序列切分。 LIS 有一个孪生问题:把序列切成最少条递增子序列,最少切几条?答案是最长下降子序列的长度,背后是 [ Rbook: 偏序与Dilworth定理]。

练习题目

基础模板与性质

[ luogu B3637: 最长上升子序列] (洛谷 B3637) 基础 $O(n^2)$ 模板
[ noi_openjudge ch0206-1759: 最长上升子序列]
[ luogu P1020: [NOIP 1999 提高组] 导弹拦截] (洛谷 P1020) 必刷经典： $O(n \log n)$ 贪心二分优化与 Dilworth 定理
[ noi_openjudge ch0206-4982: 踩方格]

经典建模与变式

[ luogu P1091: [NOIP2004 提高组] 合唱队形] (洛谷 P1091) 双向 LIS（峰形序列）
[ roj 1264: 【例9.8】合唱队形]
[ luogu P2782: 友好城市] (洛谷 P2782) 航线不交叉模型（二维排序转 LIS）
[ roj 1263: 【例9.7】友好城市]
[ leetcodecn russian-doll-envelopes: 俄罗斯套娃信封问题] (LeetCode 354) 二维偏序模型（宽升序、同宽高降序）

跨主题综合优化

[ luogu P1439: 【模板】最长公共子序列] (洛谷 P1439) 全排列 LCS 位置映射转 LIS，优化至 $O(n \log n)$