day55 最长递增子序列 最长连续递增子序列 最长重复子数组
题目1 300 最长递增子序列
题目链接 300 最长递增子序列
题意
找到整数数组nums的最长严格递增子序列的长度（子序列并不改变原始的顺序，但是可以删除元素）
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i] 表示以nums[i]为结尾的最长递增子序列的长度
2）dp数组初始化
根据定义 长度至少是1 dp[i] = 1
3）递推公式
j从0到i-1各个位置的最长升序子序列 + 1 的最大值
要计算每个当前值dp[i]与现在遍历的nums[j]的长度的大小关系 每一个值都要进行比较
if(nums[i] > nums[j]) dp[i] = max(dp[j]+1，dp[i])
4）遍历顺序
根据递推公式 当前长度依赖于之前的结果 i从小到大遍历 j的遍历顺序无所谓，只要把i-1的范围内的值遍历完就ok
for(i=1；i<nums.size(); i++){
for(j=0；j<i；j++){
}
}
5）打印dp数组
代码
class Solution {
public:int lengthOfLIS(vector<int>& nums) {//定义dp数组 初始化vector<int> dp(nums.size(), 1);int result = 0;for(int i = 0; i < nums.size(); i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]) dp[i] = max(dp[j] + 1, dp[i]);}result = max(result, dp[i]);}return result;}
};- 时间复杂度: O(n^2)
- 空间复杂度: O(n)
题目2 674 最长连续递增子序列
题目链接 674 最长连续递增序列
题意
找到未排序的整数数组的最长且连续递增的子序列的长度（不能删减元素了）
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i] 表示以nums[i]为结尾的最长连续递增子序列的长度
2）dp数组初始化
至少包含1个元素 dp[i] = 1
3）递推公式
只比较nums[i]与nums[i-1]即可，这样才可以保证是连续
不用去比较nums[j]与nums[i] （j是在0到i之间遍历）
if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1
4）遍历顺序
根据递推公式 dp[i]依赖于dp[i-1] 从前往后推导
5）打印dp数组
代码
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {//定义dp数组 初始化vector<int> dp(nums.size(), 1);int result = 1; //对于只有1个元素的数组for(int i = 1; i < nums.size(); i++){if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;result = max(result, dp[i]);}return result;}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
题目3 718 最长重复子数组
题目链接 718 最长重复子数组
题意
返回两个整数数组nums1和nums2的公共的最长子数组的长度
动态规划
动规五部曲
1）dp数组及下标i的含义
想到使用二维dp数组可以记录两个字符串的所有比较情况
dp[i][j] 表示以nums1[i-1]结尾的数组和以nums2[j-1]结尾的数组的公共最长子数组的长度
2）dp数组初始化
根据递推公式 初始化第一行第一列
根据dp数组定义 dp[i][0] 与 dp[0][j] 没有意义
根据递推公式 是在上一个基础上加1 应该从0开始往上加 dp[i-1][0] = 0 dp[0][j-1] = 0 其他下标可初始为任意值
3）递推公式
根据dp数组的定义 dp[i][j]以nums1[i-1]结尾 nums2[j-1]结尾 所以比较nums1[i-1]与nums2[j-1]
if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1
4）遍历顺序
遍历2个数组的顺序谁先谁后均可 只要把两个数组遍历完即可
之所以有等号，根据dp数组的定义 dp[i][j]以nums1[i-1]结尾 nums2[j-1]结尾
等号代表 nums1[nums1.size()-1] nums2[nums2.size()-1]
for(i=1；i<=nums1.size()；i++){
for(j=1；j<=nums2.size()；j++){
}
}
5）打印dp数组
代码
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {//定义dp数组 初始化dp数组vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for(int i = 1; i <= nums1.size(); i++){for(int j = 1; j <= nums2.size(); j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;}result = max(result, dp[i][j]);}}return result;}
};- 时间复杂度：O(n × m)，n 为nums1长度，m为nums2长度
- 空间复杂度：O(n × m)