子序列问题
✏️ 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 中的某个元素对齐。对于每一种对齐方式,计算它们相对位置相同的重复子数组即可。时间复杂度: 。
方法三:如果数组 A 和 B 有一个长度为 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
,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
思路:用 开表示以第 i 个元素结尾的乘积最大子数组的乘积。状态转移方程:
。这里需要 根据正负性进行分类讨论,考虑当前位置如果是一个负数的话,那么我们希望以它前一个位置结尾的某个段的积也是个负数,这样就可以负负得正,并且我们希望这个积尽可能「负得更多」,即尽可能小。如果当前位置是一个正数的话,我们更希望以它前一个位置结尾的某个段的积也是个正数,并且希望它尽可能地大。于是这里我们可以再维护一个 ,它表示以第 i 个元素结尾的乘积最小子数组的乘积,那么我们可以得到这样的动态规划转移方程:
优化空间:由于第 i 个状态只和第 i - 1 个状态相关,根据「滚动数组」思想,我们可以只用两个变量来维护 i - 1 时刻的状态,一个维护 ,一个维护 。
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]
必须被选取。则状态转移方程为:
思路二:二分查找:
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 ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
进阶:设计并实现时间复杂度为 的解决方案吗?
✏️ 3、循环连续子序列问题
🖋️ 3.1、彩色宝石项链
最后更新于
这有帮助吗?