Lis问题

Published: May 23, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 动态规划解决LIS问题
• 平衡树解决LIS问题
• 最长递增子序列和最小递减序列划分
• 置换的递增/递减子序列分解
• LIS的期望长度
• 构造递增递减子序列
• LIS的必要点

动态规划解决LIS问题

给定一个序列$a_1,a_2,\ldots, a_n$，找出其中最长的一段子串$b_1,b_2,\ldots, b_k$，使得该子串严格递增。

这个问题的解决方法非常多，比如说用动态规划，定义$dp(i)$表示以第$a_i$结尾的子串中最长的子串长度，那么很显然有递推公式：

$$dp(i)=\max_{j<i\land a_j<a_i}dp(j)$$

这个转移可以用线段树进行优化，优化后的时间复杂度为$O(n\log_2n)$。

讲另外一种二分的做法。定义$f_i(j)$表示仅考虑序列前$i$个元素，所有长度为$j$的递增子序列的最后一个元素的最小值。

很显然必定有$f_i(j)\geq f_i(j-1)$，$f_i(j)\geq f_{i-1}(j)$。因为存在长度为$j$的子序列，删除其中任意一个元素，一定可以得到另外一个长度为$j-1$的子序列。

因此，考虑第$i$个数$a_i$的时候，我们需要找到最大的$j$满足，$f_{i-1}(j)<a_i$，由于$f_{i-1}$是递增函数，因此二分是适用的。我们可以保证$f_i(j+1)=a_i$，而对于其余的值$t\neq j+1$，一定有$f_i(t)=f_{i-1}(t)$。因为假如$f_i(j+1)$小于$a_i$，那么一定有$f_{i-1}(j+1)=f_i(j+1)<a_i$，这与之前$j$最大相悖。

平衡树解决LIS问题

平衡树也可以用于解决LIS问题。具体做法就是在平衡树的第$k$个顶点关键字表示$dp(k)$，即构建长度为$k$的递增子序列，最后一个数字最小能是多少。那么考虑处理下一个数$x$的时候。我们需要清理掉关键字大于等于$x$的最小的顶点，并将$x$插入到平衡树中。

稍微说一下原因，我们从转移的角度来考虑问题，当遇到$x$的时候，如果$dp(k)<x$，则可以尝试将$dp(k+1)$优化到$x$。这样我们将$dp$序列切成两部分，第一部分中所有顶点关键字小于$x$，其余顶点在第二部分。很显然只有第一部分的最后一个顶点可以转移成功，设$l$为第一部分的长度，则转移为$dp(l+1)=x$。考虑第二部分发生的变化，如果第二部分中含有关键字为$x$的顶点，则插入$x$无影响，但是我们出于简便考虑，直接将其删除即可。同理如果第二部分没有含有关键字为$x$的顶点，考虑其中最小的顶点所代表的含义为$dp(l+1)>x$，我们发现这东西已经没用了，将其删除即可。

TreeSet<Integer> set = new TreeSet();
for(int x : a){
  Integer ceil = set.ceiling(x);
  if(ceil != null){
    set.remove(ceil);
  }
  set.add(x);
}

很显然平衡树解决LIS的时间复杂度为$O(n\log_2n)$。可以发现平衡树版本的实现更加简单。实际上平衡树版本还能解决LIS的扩展版本问题。

给定$n$个区间，第$i$个区间为$[l_i,r_i]$。要求从每个区间选择一个数，记第$i$个区间选择的数为$x_i$。于是我们得到了一个序列$x_1,\ldots,x_n$，问这个序列的LIS长度。其中$n\leq 10^6, 1\leq l_i\leq r_i\leq 10^{18}$

我们可以维护相同的一个平衡树，其中每个顶点的含义是相同的。但是现在我们要处理的是区间而非一个点。我们可以将整个平衡树切分成三部分，$L$中存储关键字小于$l$的顶点，$M$中存储关键字落在$[l,r-1]$中的顶点，而其余顶点存在$R$中。考虑这三部分会发生怎样的改变，很显然插入这个区间对于$L$中顶点不会产生影响。而对于$M$，我们可以在前面插入一个新的顶点$l-1$，之后将$M$中的顶点的关键字全部增加$1$（这个可以用惰性标记）。对于$R$，由于$M$增大了$1$，因此它的第一个顶点，含义是$dp(|L|+|M|)\geq r$，这个顶点可以被删除（因为和$M$中最后一个顶点冲突）。

最后的结果就是平衡树中有多少顶点。总的时间复杂度为$O(n\log_2n)$。

最长递增子序列和最小递减序列划分

如果我们可以将序列划分为若干个子序列，每个子序列都严格递减，那么称这是一个递减序列划分。所有递减序列划分中，划分的子序列最少的称为最小递减序列划分。

定理：一个序列的最长非严格递增子序列长度等于该序列的最小递减序列划分大小

首先我们建立$dp[i]$，表示所有长度为i的递增序列的最小末端元素，很显然在用二分法优化DP的时候$dp[i]$是不断递减的，而有意义的$dp$仅为$dp[1],dp[2],\ldots,dp[m]$，其中m是LIS的长度。因此我们可以发现对于固定的$k$，加入到$dp[k]$中的元素构成了一个递减子序列，而这些$m$个子序列构成了原来序列的一个划分。

这样我们就证明了划分的存在，现在我们证明不可能存在更小的划分。实际上，考虑一个LIS对应的序列$b_1,b_2,\ldots, b_m$，容易发现任意两个元素不能处于同一个递减子序列中，因此递减子序列数至少为$m$。

引理：一个序列的最长非严格递减子序列长度等于该序列的最小递增序列划分

置换的递增/递减子序列分解

对于$1,2,\ldots, n$的所有置换，我们希望将序列分解为最少的一些子序列，要求这些子序列满足递增或递减性质（分解的不同子串可以分别满足递增和递减）。考虑$1,2,\ldots,n$的所有置换，它们中最小分解的最大值$f(n)$是多少。

可以证明这个值是最小的正整数$k$，满足$\frac{k(k+1)}{2}\geq n$。

用归纳法证明，当$n=1$的时候，$k=1$，命题一定成立。

考虑任意$n$，假设其LIS长度大于等于$k$，那么我们就可以从中提取出LIS作为一个划分的一部分，于是最少划分数量为$f(n-k)+1$，此时有$\frac{k(k+1)}{2}\geq n\Rightarrow \frac{k(k-1)}{2}\geq n-k$。因此$f(n-k)=k-1$，故$f(n)=k$。

那么如果LIS长度小于等于$k$呢，由于最小递减子序列划分数等于最长递增子序列长度，因此我们可以正好将整个序列划分为$k$个递减子序列。

LIS的期望长度

题目1：给定$n$个未知数$x_1,\ldots,x_n$，其中已知$x_i$在范围$[l_i,r_i]$中均匀分布，且每个未知数都是独立的。现在要求计算序列$x_1,\ldots,x_n$的最长严格递增子序列的长度的期望。其中$1\leq n\leq 8$。

提供一道题目。

一般计算LIS是没法和期望一起算的，因为不能和期望的线性性质结合。具体的做法就是暴力枚举所有可能的排列，从而摆脱需要计算LIS带来的影响。总共有$n!$种排列，排列$p_1,\ldots,p_n$的意思是将所有未知数从小到大排列后的结果，如果$x_i=x_j$，则按照$i,j$的大小倒向排序。

在已知排列信息的前提下，可以发现序列$x_1,\ldots,x_n$的LIS对应于$p_1,\ldots,p_n$的LIS。

接下来问题就变成了已知$x_{p_1}\leq x_{p_2}< x_{p_3}\ldots$且$l_i\leq x_{i}\leq r_i$，问有多少种方案。这个是经典问题，做法就是可以发现未知数的取值区间可以划分为$O(n)$个连续段，每个未知数在每个段上要么都能取到，要么都不能取到。之后记$dp(i,j)$表示在前$i$个连续段上分配$j$个未知数的方案数。这个可以$O(n^4)$计算的到。

时间复杂度为$O(n!n^4)$。

构造递增递减子序列

题目1：给定$n,a,b$，要求构建一个$1$到$n$的排列，其中最长递增子序列的长度为$a$，而最长递减子序列的长度为$b$，要求输出这样的一个序列，或则报告无解。其中$1\leq n,a,b\leq 10^5$。

首先由于任意递增序列和递减序列最多有一个交点，因此$n\geq a+b-1$是必要条件。下面我们证明$n\leq ab$也是必要条件。考虑一个满足条件的排列，记$f(i)$表示以$i$结尾的最长递增子序列的长度，那么对于给定的$1\leq x\leq a$，可以发现满足$f(i)=x$的所有$i$组成的子序列是递减的，而这实际上将所有的元素划分到了$a$个分组中。由于每个分组最多有$b$个元素，因此一定有$ab\geq n$成立。

下面考虑如何构造这样的一个序列。首先我们构造一个长度为$ab$的序列：$b,b-1,\ldots,1,2b,2b-1,\ldots,b+1,3b,\ldots, ab,ab-1,\ldots, (a-1)b+1$。可以发现这个序列的最长递增子序列长度为$a$，最长递减子序列长度为$b$，我们需要做的就是从前面$a-1$个递减序列中删除一些元素，使得总数达到$n$。

一道题目。

LIS的必要点

给定一个序列$a_1,a_2,\ldots,a_n$，我们记$best$为整个序列的最长递增子序列的长度。那么如果我们从序列中删除元素$a_i$，会导致序列的最长递增子序列长度减少为$best-1$，则称$i$为序列的必要点。

下面我们设计一个算法来计算所有必要点。

我们记录$R(i)$表示以$a_i$作为结尾的最长递增子序列的长度。

一个点是必要点，当且仅当至少一个最长递增子序列包含这个点，并且所有最长递增子序列都包含这个点。后者我们重新表述为可以对于所有至少出现于一个最长递增子序列中的点$j$，$R(i)=R(j)\Rightarrow i=j$。

我们首先找出有哪些点被最长递增子序列包含。如果$i$出现在最长递增子序列中，当且仅当存在$j>i$，且$R(i)+1=R(j)$，且$a_i\lt a_j$，且$j$出现在最长递增子序列中，或者$D(i)=best$。我们可以从后往前倒推，可以在线性时间复杂度内得到所有结果。

总的时间瓶颈在计算$R$的过程中，这个可以直接二分+DP玩成，时间复杂度为$O(n\log_2n)$。

提供一道问题。