最长上升子序列（LIS）

前言
¶

最长上升子序列（LIS）是讲解动态规划算法的经典例题，使用朴素的动态规划算法可以在 $O (N^{2})$ 复杂度内求解；使用单调栈优化可以进一步将复杂度优化到 $O (N \log N)$ 。此外，不存在重复字符的最长公共子序列问题（LCS）可以转化成最长上升子序列问题进行求解，这使得部分 LCS 也可以在 $O (N \log N)$ 复杂度内求解，相关内容在最长公共子序列（LCS）中进行了讨论，此处不再赘述。

一些定义：

上升子序列：对于数列 $A = {a_{1}, a_{2}, \dots, a_{N}}$ ，若其某一子序列 $B = {a_{b_{1}}, a_{b_{2}}, \dots, a_{b_{M}}}$ 满足 $b_{i} < b_{i + 1}$ 且 $a_{b_{i}} < a_{b_{i + 1}}$ ，则称 $B$ 为 $A$ 的一个上升子序列。
最长上升子序列：上升子序列中元素个数最多的那些。
字典序最小的最长上升子序列：最长上升子序列中（不妨设元素个数为 $M$ ），元素下标组成的 $M$ 维向量最小的那个。

最长上升子序列的长度
¶

动态规划
¶

记 $d p_{i}$ 表示前 $i$ 个数中以第 $i$ 个数结尾的最长上升子序列长度，则状态转移方程为：

d p_{i} = max {d p_{x} | 1 ⩽ x < i, a_{x} < a_{i}} + 1

时间复杂度： $O (N^{2})$
额外空间复杂度： $O (N)$

findLengthOfLIS.1.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
export function findLengthOfLIS(
  N: number,
  cmp: (i: number, j: number) => -1 | 0 | 1 | number,
): number {
  if (N <= 0) return 0

  const dp: number[] = new Array(N)
  for (let j = 0, i: number, count: number; j < N; ++j) {
    for (i = 0, count = 0; i < j; ++i) {
      if (cmp(i, j) < 0) {
        if (count < dp[i]) count = dp[i]
      }
    }
    dp[j] = count + 1
  }
  return dp[N - 1]
}

单调栈优化
¶

维护一个单调栈 $S$ ，扫描数列 $A$ ，若 $a_{i}$ 大于栈顶元素，则压栈，否则替换掉 $S$ 中第一个大于等于 $a_{i}$ 的元素 $S_{x}$ 。则扫描完毕后， $S$ 长度即为 $A$ 的最长上升子序列的长度。因为 $S$ 是单调栈，所以可以使用二分搜索 (lower_bound) 快速找到 $S_{x}$ 。

由于对数组进行了一次 $O (N)$ 遍历，对于每个遍历到的元素都执行了一次二分查找和常数次比较、更新操作，因此：

时间复杂度： $O (N \log N)$
额外空间复杂度： $O (L)$ ， $L$ 为最长上升子序列的长度

findLengthOfLIS.2.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import { lowerBound } from '@algorithm.ts/binary-search'

type ICompare<T> = (x: number, y: number) => number

export function findLengthOfLIS(N: number, cmp: ICompare<number>): number {
  if (N <= 0) return 0

  const stack: number[] = [0]
  for (let i = 1; i < N; ++i) {
    const idx: number = lowerBound(0, stack.length, x => cmp(stack[x], i))

    // Update the monotonous stack.
    if (idx < stack.length) stack[idx] = i
    else stack.push(i)
  }
  return stack.length
}

字典序最小的最长上升子序列
¶

在上一个问题中，我们可以获得以 $a_{i}$ 结尾的最长上升子序列长度，在此基础上找到一个LIS 是简单的：

令 $i = d p (N)$
若 $d p (i) = 1$ ，则停止算法
找到一个 $j < i$ 满足 $d p (i) = d p (j) + 1$ 且 $a_{j} < a_{i}$
令 $i = j$ ，执行 2.

不难证明，收集上述算法中所有出现过的 $i$ 即可得到原数列一个 $L I S$ （下标列表）。由于 $i$ 总是在减少，所以算法复杂度为 $O (N)$ 。

接下来考虑如何获得一个字典序最小的最长上升子序列。为方便叙述，不妨记字典序最小的最长上升子序列为 $T_{0}$ ，其长度为 $l$ ，并记构成它的元素在原数列中的下标依次为： $T = t_{1}, t_{2}, \dots t_{l}$ 。

不难想到， $T$ 中最后一个元素必然是满足 $d p (i) = l$ 的最小的 $i$ ，即 $t_{l} = i$ 。而 $t_{l - 1}$ 为满足 $d p (j) = l - 1$ 且 $j < t_{l}$ 的最小的 $j$ ；以此类推。于是可以得到如下算法：

维护一个长度为 $l$ 的数列 $R = {r_{1}, r_{2}, \dots r_{l}}$ ，数列中所有元素的初始值均为 $- 1$ ；
从 $N$ 到 $1$ 遍历 $i$ ，对于每个 $i$ 均执行 3；
记 $x = d p (i)$ ，若 $x = l$ ，则直接将 $R_{x}$ 更新为 $i$ ，因为它参与构成的最长上升子序列的字典序肯定比之前找到的 $R_{l}$ 更优。否则， $x < l$ ，此时需要检查一下是否已经找到了一个合法的 $R_{x + 1}$ ，即以 $a_{R_{x + 1}}$ 作为结尾的最长子序列长度为 $x + 1$ ：
- 若存在且 $a_{i} < a_{R_{x + 1}}$ ，则将 $R_{x}$ 更新为 $i$ ，因为它肯定比之前找到的 $R_{x}$ 更优（从字典序上来看）；
- 否则，抛弃 $i$ ，不做任何操作。

ATTENTION

综上所述，求最小字典序的最长上升子序列的算法为求最长上升子序列的长度的算法基础上加一次 $O (N)$ 遍历，因此它们的总体复杂度相同^[1]。

下面两个算法中给出的代码实现都是求 $T$ 而非 $T_{0}$ ，即返回值为构成最小字典序的最长上升子序列的元素其在原数列中的下标列表。如需获得实际的元素，可以自行映射，如：

getMinimumLexicographicOrderLIS.ts

1
2
3
4
5
6
7
function getMinimumLexicographicOrderLIS(nums: number[]): number[] {
  const idx: number = findMinimumLexicographicOrderLIS(
    nums, 
    (x, y) => x - y
  )
  return idx.map(id => nums[id])
}

动态规划
¶

findMinimumLexicographicOrderLIS.1.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
export function findMinimumLexicographicOrderLIS(
  N: number,
  cmp: (i: number, j: number) => -1 | 0 | 1 | number,
): number[] {
  if (N <= 0) return []

  const dp: number[] = new Array(N)
  for (let j = 0, i: number, count: number; j < N; ++j) {
    for (i = 0, count = 0; i < j; ++i) {
      if (cmp(i, j) < 0) {
        if (count < dp[i]) count = dp[i]
      }
    }
    dp[j] = count + 1
  }

  const results: number[] = new Array(dp[N - 1]).fill(-1)
  for (let i = N - 1; i >= 0; --i) {
    const idx = dp[i] - 1
    if (idx + 1 < results.length) {
      if (results[idx + 1] === -1 || cmp(i, results[idx + 1]) >= 0) continue
    }
    results[idx] = i
  }
  return results
}

单调栈优化
¶

需要额外维护一个数组（对应下面代码中的 rank 数组），其含义与前面动态规划解法的 dp 数组类似： $r a n k (i)$ 表示前 $i$ 个数中以第 $i$ 个数结尾的最长上升子序列长度 $- 1$ 。

findMinimumLexicographicOrderLIS.2.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import { lowerBound } from '@algorithm.ts/binary-search'

type ICompare<T> = (x: number, y: number) => number

export function findMinimumLexicographicOrderLIS(N: number, cmp: ICompare<number>): number[] {
  if (N <= 0) return []

  const rank: number[] = new Array(N)
  const stack: number[] = []
  for (let i = 0; i < N; ++i) {
    const idx: number = lowerBound(0, stack.length, x => cmp(stack[x], i))
    rank[i] = idx

    // Update the monotonous stack.
    if (idx < stack.length) stack[idx] = i
    else stack.push(i)
  }

  stack.fill(-1)
  for (let i = N - 1; i >= 0; --i) {
    const idx = rank[i]
    if (idx + 1 < stack.length) {
      if (stack[idx + 1] === -1 || cmp(i, stack[idx + 1]) >= 0) continue
    }
    stack[idx] = i
  }
  return stack
}

最长非严格递增子序列
¶

和上升子序列相比只改变了一个条件，即目标序列中相邻元素不再是严格小于，而是小于等于。不难得到新的状态转移方程：

d p_{i} = max {d p_{x} | 1 ⩽ x < i, a_{x} ⩽ a_{i}} + 1

TIP

观察转移方程的变化，不难想到可以通过修改 cmp 函数的定义（也就是把“小于等于”都视作小于）来支持上文提到的算法求解最长严格非递增子序列问题，如：

findLengthOfLNIS.3.ts

1
2
3
4
5
6
export function findLengthOfLNIS(
  N: number,
  cmp: (i: number, j: number) => -1 | 0 | 1 | number,
): number {
  return findLengthOfLIS(nums, (i, j) => cmp(i, j) <= 0 ? -1 : 1) 
}

动态规划
¶

findLengthOfLNIS.1.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
export function findLengthOfLNIS(
  N: number,
  cmp: (i: number, j: number) => -1 | 0 | 1 | number,
): number {
  if (N <= 0) return 0

  const dp: number[] = new Array(N)
  for (let j = 0, i: number, count: number; j < N; ++j) {
    for (i = 0, count = 0; i < j; ++i) {
      if (cmp(i, j) <= 0) {
        if (count < dp[i]) count = dp[i]
      }
    }
    dp[j] = count + 1
  }
  return dp[N - 1]
}

单调栈优化
¶

只要把 lowerBound 改成 upperBound 就好了。

findLengthOfLNIS.2.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import { upperBound } from '@algorithm.ts/binary-search'

type ICompare<T> = (x: number, y: number) => number

export function findLengthOfLNIS(N: number, cmp: ICompare<number>): number {
  if (N <= 0) return 0

  const stack: number[] = [0]
  for (let i = 1; i < N; ++i) {
    const idx: number = upperBound(0, stack.length, x => cmp(stack[x], i))

    // Update the monotonous stack.
    if (idx < stack.length) stack[idx] = i
    else stack.push(i)
  }
  return stack.length
}

前言¶

最长上升子序列的长度¶

动态规划¶

单调栈优化¶

字典序最小的最长上升子序列¶

动态规划¶

单调栈优化¶

最长非严格递增子序列¶

动态规划¶

单调栈优化¶

Related¶

前言
¶

最长上升子序列的长度
¶

动态规划
¶

单调栈优化
¶

字典序最小的最长上升子序列
¶

动态规划
¶

单调栈优化
¶

最长非严格递增子序列
¶

动态规划
¶

单调栈优化
¶

Related
¶