最长公共子序列（LCS）与最长上升子序列（LIS）问题的相互转换

在此只做直观理解，不做严格证明
参考：LCS 问题与 LIS 问题的相互关系，以及 LIS 问题的最优解证明

LCS转LIS

LCS转LIS只能对特殊情况适用。即当LCS中两个数组有一个不存在重复元素的情况下才能进行转换。
我们以一个例子进行说明，假设有如下两个数组A和B, A不存在重复元素：
A：

B：

假设A和B的公共子序列为 [1, 8, 7]。其中a,b,c,d,e都是一些不影响上述假设的数字，为了更容易理解，这里用字母代替。
我们把B中的元素都换成在A中的下标，因为A[1] = 1, A[3] = 8, A[5]=7, 即得到一个新的数组C如下：
C：

对C求最长上长子序列，得到[1, 3, 5]。再它再映射到A中，即最终得到序列：
[A[1], A[3], A[5]] = [1, 8, 7]。我们发现通过LIS求得的序列与LCS相同。

LIS转LCS

同样使用一个例子说明
假设有数组A如下：

显然，最长上升子序列为 [1, 3, 5, 7]。我们对它做一个排序，得到数组B：

求A，B的最长公共子序列得 [1,3,5,7]。与LIS求得的结果相同。

直观理解就是：LIS相互之间其实是有序的，排序后并不会破坏这种顺序。而且排序后一定不存在更长的LCS，如果有的话，那它一定比LIS更长，矛盾！

LCS的解法

使用动态规划，以leetcode 为例： LCR 095. 最长公共子序列
。假设有s[1…m]和t[1…n]两个字符串序列，用dp[i][j] 表示s[1…i]和t[1…j]的最长公共子序列的长度。则状态转移方程如下：
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] i f   s i = t i m a x { d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] } e l s e dp[i][j] = \left\{

\right . dp[i][j]={dp[i−1][j−1]max{dp[i][j−1],dp[i−1][j]}​if si​=ti​else​

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                char a = text1.charAt(i-1);
                char b = text2.charAt(j-1);
                if(a == b){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度$O(mn)$
空间复杂度$O(mn)$, 可以用滚动数组进一步优化到O(n), 此处略

LIS 的解法

参考leetcode 300. 最长递增子序列

假设有序列a[1…n], 要求它的最长上升子序列。

朴素解法-动态规划

我们用dp[i] 表示a[1…i] 的最长上升子序列，则状态转移方程如下：

d p [ i ] = { max ⁡ j ∈ [ 1.. i − 1 ] ∧ a j < a i { d p [ j ] + 1 } i f   { j ∣ a j < a i } ≠ ∅ 1 e l s e dp[i] = \left\{

\right . dp[i]={maxj∈[1..i−1]∧aj​<ai​​{dp[j]+1}1​if {j∣aj​<ai​}=∅else​

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
        }
        int max = 0;
        for(int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

优化解法-动态规划+二分查找

首先定义函数$g(i)$ 表示在长度为i的所有上升子序列中，最小的最后一个元素。例如数组[1,2,7,5] 有下面两个长度为3的上升子序列： [1,2,7] 、[1,2,5]。它们最后一个元素分别为 7、5其中最小的是5，所以根据定义 g(3) = 5。

那么我们的目的就是需要构建这样一个函数。可以通过反证法证明这个函数一定是单调的。请参考：LCS 问题与 LIS 问题的相互关系，以及 LIS 问题的最优解证明。

构建的方法是不断地从原数组中读取一个数字，然后更新认知。
初始时 g 是一个空的数组，然后不断地添加或更新。假设某一个时刻读取到的数字是 $a_j$。因为g是单调的，因此我们可以通过二分查找找到最接近$a_j$的g(i) 使得$g(i)<a_j$。显然我们可以在长度为$i$的上升子序列基础上拼接$a_j$得到一个长度为$i+1$的上升子序列， 因此令

g ( i + 1 ) = { a j 如果  g ( i + 1 ) 未初始化 min ⁡ { g ( i + 1 ) , a j } 否则 g(i+1) = \left\{

\right . g(i+1)={aj​min{g(i+1),aj​}​如果 g(i+1)未初始化否则​
为了编程方便，g通常初始化为一个非常大的值，例如，Integer.MAX_VALUE， 且 g(i+1) 如果已经初始化，因为g(i)是所有小于$a_j$的数中最大的，则g(i+1)一定大于等于$a_j$。所以可以直接令：

$$g(i+1)=a_j$$

凝练成代码如下

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] g = new int[n+1]; // g[i]表示长度为i的上升子序列中最小的一个结尾元素，参考宫水三叶
        for(int i = 1; i <= n; i++){
            g[i] = Integer.MAX_VALUE;
        }
        int max = 0;
        for(int i = 0; i < n; i++){
            int l = 0;
            int r = i+1;
            while(l + 1 < r){
                int mid = (l + r) >> 1;
                if(g[mid] >= nums[i]){
                    r = mid;
                }else{
                    l = mid;
                }
            }
            g[r] = nums[i];
            max = Math.max(max, r);
        }
        return max;
    }
}
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

时间复杂度$O(n{\log }_{2}n)$
空间复杂度$O(n)$

LIS的应用

以 leetcode 334. 递增的三元子序列 为例。

解法一：求LIS，判断LIS是否大于等于3。时间复杂度$O(n{\log }_{2}n)$, 空间复杂度$O(n)$。代码略。
解法二：考虑到只需要判断有没有长度为3的子序列，因此在求LIS时只需要维维g(1)和g(2)即可，当发现需要赋值g(3)时，说明存在长度为3的上升子序列，直接返回true。代码如下。时间复杂度$O(n)$, 空间复杂度$O(1)$。

class Solution {
    // g[i] 表示长度为i的上升子序列的最小【结尾元素】 
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        int g1 = Integer.MAX_VALUE;
        int g2 = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            if(nums[i] > g2) return true;
            else if(nums[i] > g1) g2 = nums[i];
            else g1 = nums[i]; 
        }
        
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15