您的位置: 首页  >  IT文章  >  最长上升子序列 LIS (Longest Increasing Subsequence)

最长上升子序列 LIS (Longest Increasing Subsequence)

分类: IT文章 • 2022-04-25 22:39:42

已知一个有N个数的数列(a_0, a_1, ..., a_{N-1})，且(forall a_i, exists a_iinmathbb N^*)。求该数列的一个子序列(b_0, b_1, ..., b_{M-1})，使(b_0≤b_1≤ ...≤b_{M-1})，且M尽量大。注意：子序列意思是(b_i, b_{i+1})映射到(a)的编号不一定连续，但相对位置不变。
【输入】N，数列(a).
【输出】M

(O(N^2+NlogN))：转化为LCS

问题可转化为：求原序列(a)与将(a)从小到大去重排序后的新序列(a')的LCS。如果问题是不下降/不上升子序列就不用去重了。
(TODO)

(O(N^2))：动态规划

在逐个加入元素的角度考虑，先假设已经加入了(a_0, a_1, ..., a_{i-1})，形成了一些上升子序列。现在要加入(a_i)。
那么，很明显可以想到一个算法：将(a_i)连到一个结尾元素比它小的上升子序列后面，如果有多个，连到最长的一个后面。
用(f_i)表示结尾元素（在数列a中）下标是 (i) 的LIS的长度，那么有两种情况：

  • (a_i)比 (a) 前面任何一个元素都小，此时(f_i=1)；
  • (a_i) 比前面的一些元素（或全部元素）大，此时(a_i)应该连接到以这些元素结尾的子序列中最长者的结尾，并且该子序列长度+1，即(f_i=displaystylemax_{substack{j<i\a_j<a_i}}{f_j}+1)

于是得状态转移方程：$$f_i=max_{substack{j<ia_j<a_i}}{f_j}+1$$

f[0] = 1;
for (i = 1; i < N; i++)
{
  for (j = 0; j < i; j++)
    if (a[j] < a[i])
      f[i] = max(f[i], f[j] + 1);
  LIS_len = max(LIS_len, f[i]);
}

若f[i]表示结尾元素下标(≤i)的LIS的长度，可以减少代码量，但时间复杂度没有优化。

f[0] = 1;
for (i = 1; i < N; i++)
  for (j = 0; j < i; j++)
    f[i] = max(f[i], f[j]+a[j]<a[i]);

(O(N log N))：动态规划+树状数组/线段树优化+离散化

要从(O(N^2))进化到(O(N log N))，需要突破刚才DP的思维，从另一种角度DP（改变(f_i)的意义，推出更快的递推式）。
同样假设已经加入了(a_0, a_1, ..., a_{i-1})，现在要加入(a_i)。设(f_h)表示结尾元素的高度为(h)的LIS的长度。显而易见，$$f_{a_i}=max_{substack{1≤j<{a_i}j<i}}f_j+1$$注意max的定义域里俩条件的顺序，第一条件是j＜元素(i)的高度，第二条件才是(j<i)。考虑到( equire{enclose}enclose{horizontalstrike}{f_{a_j}mid j>i})必然为0（←若(a_k=a_j(k<i<j))，(f_{a_j})即(f_{a_k})不为0）求(f_{a_i})显然与(f_{a_j}(j>i))无关（但和(f_{a_k}(k<i))有关），则只剩下了求(displaystylemax_{1≤j<{a_i}}f_j)。还不够明显？也就是求(max (f_1,f_2,...,f_{a_i-1}))！所以该递推式被转化为了RMQ，而众所周知，线段树正支持在(O(logN))的时间内进行单点修改的RMQ。

下一个问题。如果(a_i≤2*10^6)，建一棵有(2*10^6)个叶结点的线段树并不困难（被卡空间的可能性也不大），但如果(a_i≤10^9)，空间就炸了。考虑到正常题目中(N)至多(≤2*10^6)（否则输入数据的时间都是个问题），即至多只有(2*10^6)个高度，(f)中至多也只有(2*10^6)个有效的下标。因此，

下一个问题。

用(a''_i)表示(a_i)是(a)中第几小的元素。
虽然说树状数组不能处理RMQ，但可以处理前缀的最大值！

模仿解决RMQ的树状数组，设树状数组 (c) 的值由

$$egin{align*}
c_1 &= f_i mid a''_i=1 & c_5 &= f_i mid a''_i=5\
c_2 &= min_{a''_i in {1,2}}{f_i} & c_6 &= min_{a''_i in {5,6}}{f_i}\
c_3 &= f_i mid a''_i=3 & c_7 &= f_i mid a''_i=7\
c_4 &= min_{a''_i in {1...4}}{f_i} & c_8 &= min_{a''_i in {1...8}}{f_i}
end{align*}
$$

函数条件比较奇怪。应该理解为由(a''_i)的取值范围确定(i)的取值，再由(i)的取值确定是计算哪些(f_i)的最小值。
(TODO)

(O(N log N))：动态规划+单调性+二分查找

还有一种DP的思维。设(f_i)表示长度为(i)的LIS中，高度最小的结尾元素的值。这种算法中，为什么(f_i)记录最小结尾元素和为什么(f)数组能保持单调性是两个难点。
我们期望在前i个元素中的所有长度为len的递增子序列中找到这样一个序列，它的末尾元素比(a_i)小，而且长度要尽量的长，如此，我们只需记录len长度的递增子序列中最大元素的最小值，就能使得将来的递增子序列尽量地长。
举个例子，还是在逐个加入元素的角度考虑，在加入(a_i)前，(a_0)到(a_{i-1})组成的LIS有两条，但是结尾元素一个是10，一个是20。
加入(a_i)后，如果 (a_i≤10)，那两个都不能加；如果 (a_i>20) ，两个LIS加哪个也无所谓。但如果(10<a_i≤20)，那么很明显只能选结尾元素是10的LIS。若(a_0)到(a_{i-1})还可以组成第三个结尾元素是5的LIS，结尾元素是5，很明显选它更优。
上面这个例子说明在相同长度的前提下，LIS的结尾元素越小越好。因此，用 (i) 表示LIS的长度，(f_i) 表示最小结尾元素方便了后面元素的查询。每加入一个元素，查询符合的LIS，再更新，使得数组的单调性不会影响，因为较长的上升子序列是由较短的上升子序列连接元素组成，比如，当 (f_3=5) 时， 只要有长度为4的LIS，必定有(f_4>5)，因为这个LIS的第3个元素至少是5，因而它的第四个元素必然大于5。
C++的<algorithm>库里就有两个二分搜索的函数。
lower_bound(first, last, val)函数返回单调递增序列[first, last)（包含 first 不包含 last）中的第一个大于等于值val的位置。first与last均为指针类型，使用时类似sort，下同。
upper_bound(first, last, val)函数返回单调递增序列[first, last)中第一个大于val的位置。
这两个函数的时间复杂度都是(O(log N))。

f[0] = -oo;
f[1] = a[0];
for (i = 2; i < N; i++)
  f[i] = oo;
for (i = 1, ans = 1; i < N; i++)
{
  int* p = lower_bound(f, f + ans + 2, a[i]);
  if (a[i] < *p)
    *p = a[i];
  if (f[ans + 1] < oo)
    ans++;
}

五、为什么要写这么多种方法

  1. 观察某个问题的不同思路。思路不同，效率千差万别。
  2. 观察建立在某种方法上的优化与优化+优化+优化+……。
  3. 提高把某个问题规约到已知问题的能力。

相关推荐