子序列问题

✏️ 1、连续子序列问题

🖋️ 1.1、最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

方法一：动态规划： dp[i][j] 表示长度为 i，末尾项为 A[i-1] 的子数组，长度为 j，末尾项为 B[j-1] 的子数组，二者的最大公共后缀子数组长度。如果 A[i-1] != B[j-1]，dp[i][j] = 0 如果 A[i-1] == B[j-1] ，dp[i][j] = dp[i-1][j-1] + 1 。

base case：如果 i==0 || j==0，其中一个数组长度为 0，没有公共部分，dp[i][j] = 0 最长公共子数组以哪一项为末尾项都有可能，即每个 dp[i][j] 都可能是最大值。

方法二：滑动窗口：枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式，计算它们相对位置相同的重复子数组即可。时间复杂度： $O((N + M) \times \min(N, M))$ 。

方法三：如果数组 A 和 B 有一个长度为 k 的公共子数组，那么它们一定有长度为 $j \le k$ 的公共子数组。这样我们可以通过二分查找的方法找到最大的 k。而为了优化时间复杂度，在二分查找的每一步中，使用哈希的方法来判断数组 A 和 B 中是否存在相同特定长度的子数组。（搬运一下官网的讲解）

动态规划

int findLength(vector<int>& A, vector<int>& B) {
    int ret = 0;
    int dp[B.size() + 1][A.size() + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = B.size() - 1; i >= 0; i --){
        for(int j = A.size() - 1; j >= 0; j --){
            if(B[i] == A[j]){
                dp[i][j] = dp[i + 1][j + 1] + 1;
            }
            ret = std::max(ret, dp[i][j]);
        }
    }
    return ret;
}
int findLength(vector<int>& A, vector<int>& B) {
    int ret = 0;
    int dp[B.size() + 1][A.size() + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= A.size(); i ++){
        for(int j = 1; j <= B.size(); j ++){
            if(B[i - 1] == A[j - 1]){
                // i 只与 i - 1 有关
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = 0;
            }
            ret = std::max(ret, dp[i][j]);
        }
    }
    return ret;
}
// 优化到一维数组：第二层for循环我们使用的倒序的方式，这是因为dp数组后面的值会依赖
// 前面的值，而前面的值不依赖后面的值，所以后面的值先修改对前面的没影响，但前面的值
// 修改会对后面的值有影响，所以这里要使用倒序的方式。
int findLength(vector<int>& A, vector<int>& B) {
    int ret = 0;
    int dp[B.size() + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < A.size(); i ++){
        for(int j = B.size(); j > 0; j --){
            if(A[i] == B[j - 1]){
                dp[j] = dp[j - 1] + 1;
            }else{
                dp[j] = 0;
            }
            ret = std::max(ret, dp[j]);
        }
    }
    return ret;
}

滑动窗口

二分查找

🖋️ 1.2、乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

思路：用 $f_{\max}(i)$ 开表示以第 i 个元素结尾的乘积最大子数组的乘积。状态转移方程：

$f_{max}(i) = max\{ f_{max}(i - 1) \times a_i, a_i \}$ 。这里需要 根据正负性进行分类讨论，考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个 $f_{\min}(i)$ ，它表示以第 i 个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：

$f_{max}(i) = max \{ f_{max}(i - 1) \times a_i, f_{min}(i - 1) \times a_i, a_i \}$

$f_{min}(i) = min_ \{ f_{max}(i - 1) \times a_i, f_{min}(i - 1) \times a_i, a_i \}$

优化空间：由于第 i 个状态只和第 i - 1 个状态相关，根据「滚动数组」思想，我们可以只用两个变量来维护 i - 1 时刻的状态，一个维护 $f_{max}$ ，一个维护 $f_{min}$ 。

int maxProduct(vector<int>& nums) {
    int fmax = nums[0], fmin = nums[0];
    int ret = nums[0], tmp = 0;
    for(int i = 1; i < nums.size(); i ++){
        tmp = fmax;
        fmax = max(fmax * nums[i], max(fmin * nums[i], nums[i]));
        fmin = min(tmp * nums[i], min(fmin * nums[i], nums[i]));
        ret = max(fmax, ret);
    }
    return ret;
}

✏️ 2、不连续子序列问题

🖋️ 2.1、最长递增子序列

最长递增子序列（Longest Increasing Subsequence，简写 LIS）：给定一个无序的整数数组，找到其中最长上升子序列的长度。

思路一：动态规划： dp[i] 表示以第 i 个数字结尾的最长上升子序列的长度，nums[i]必须被选取。则状态转移方程为：

$dp[i] = \text{max}(dp[j]) + 1, \text{其中} \, 0 \leq j < i \, \text{且} \, \textit{num}[j]<\textit{num}[i]$

思路二：二分查找：

动态规划

int lengthOfLIS(vector<int>& nums) {
    if(nums.empty())
        return 0;
    vector<int> dp(nums.size(), 1);
    int ret = 1;
    for(int i = 1; i < nums.size(); i ++){
        int j = i - 1;
        for(; j >= 0; j --){
            if(nums[i] > nums[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ret = max(ret, dp[i]);
    }
    return ret;
}

二分查找

🖋️ 2.2、递增子序列

给定一个整型数组，找到所有该数组的递增子序列，递增子序列的长度至少是2。

🖋️ 2.3、最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

🖋️ 2.4、最长公共子序列

最长公共子序列（Longest Common Subsequence，简称 LCS）： 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

🖋️ 2.5、最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：设计并实现时间复杂度为 $O(n)$ 的解决方案吗？

✏️ 3、循环连续子序列问题

🖋️ 3.1、彩色宝石项链