子序列问题

✏️ 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;
}

滑动窗口

int findLength(vector<int>& A, vector<int>& B) {
    int ret = 0;
    int m = A.size(), n = B.size();
    for(int i = 0; i < m; i ++){
        int p = i, q = 0;
        int len = 0;
        while(p < m && q < n){
            len = A[p] == B[q] ? len + 1 : 0;
            ret = max(ret, len);
            p++, q++;
        }
    }
    for(int i = 0; i < n; i ++){
        int p = i, q = 0;
        int len = 0;
        while(p < n && q < m){
            len = B[p] == A[q] ? len + 1 : 0;
            ret = max(ret, len);
            p++, q++;
        }
    }
    return ret;
}
// 滑动窗口算法有个小优化，每次对齐后可以计算一下长度len是否已经小于或等于结果ret，
// 如果是，那我们就不用继续循环计算了，因为后面肯定没有更长的。

二分查找

int base = 113;
int mod = 1e9 + 7;
// 求pow(base, len - 1),注意溢出问题
long helper(int i){
    long res = 1;
    long ref = base;
    while(i != 0){
        //如果是奇数次幂，先抽一个底数出来，提前乘到结果中
        if(i % 2 != 0){
            res = (res * ref) % mod;
        }
        //底数平方，幂减半
        ref = (ref * ref) %mod;
        i /= 2;
    }
    return res;
}
// 检验是否存在长度为len的公共子数组
bool check(std::vector<int>& A, std::vector<int>& B, int len){
    // 算出A[0, len - 1]的哈希值
    long hashA = 0;
    for(int i = 0; i < len; i++)
        hashA = (hashA * base + A[i]) % mod;
    unordered_set<int> setA;
    setA.insert(hashA);
    // 根据公式递推后面对应长度的哈希值，并存入哈希表
    long ref =  helper(len - 1) ;
    for(int i = 0; i < A.size() - len; i ++){
        // +mod 是为了保证 hashA 大于0
        hashA = ((hashA - A[i] * ref % mod + mod) % mod * base + A[i + len]) % mod;
        setA.insert(hashA);
    }
    // 同样的方式处理B数组
    long hashB = 0;
    for(int i = 0; i < len; i++)
        hashB = (hashB * base + B[i]) % mod;
    if(setA.count(hashB))
        return true;
    for(int i = 0; i < B.size() - len; i++){
        hashB = ((hashB - B[i] * ref % mod + mod) % mod * base + B[i + len]) % mod;
        if(setA.count(hashB))
            return true;
    }
    return false;
}
int findLength(vector<int>& A, vector<int>& B) {
    // [left, right]是所有可能不存在“对应长度的公共子数组”的集合
    // （0是一定存在的，所以left从1开始，min(A.size() , B.size()) + 1
    // 是一定不存在的，所以也需要包含在内）
    int left = 1;
    int right = min(A.size(), B.size()) + 1;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(check(A, B, mid))
            left = mid + 1;
        else
            right = mid;
    }
    return left - 1;
}

🖋️ 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、彩色宝石项链