Day45：300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
文章目录
- 300.最长递增子序列
- 思路
- 代码实现
- 674. 最长连续递增序列
- 思路
- 代码实现
- 718. 最长重复子数组
- 思路
- 代码实现
300.最长递增子序列
题目链接
思路
- 单个字符都是一个长为1的子序列，直接初始化dp为1。
- 先固定一个元素位置i，判断0-i范围内到i的最长子序列，这时nums[i]需要依次和前面每个元素相比较，如果nums[i]比某个元素nums[j]大，则最长子序列在dp[j]的前提下长度加1.
- 记录每次dp[i]更新时记录最大序列长度result
代码实现
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(),1);int result=1;for(int i=1;i<nums.size();i++){ for(int j=0;j<i;j++){if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);}if(result<dp[i])result=dp[i];}return result;}
};
674. 最长连续递增序列
题目链接
思路
思路和上一题差不多，不过上一题范围比较广0-i范围内可以跳跃性构成子序列，但这道题必须相邻，所以判断条件改为nums[i]>nums[i-1]即可。
代码实现
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(),1);int result=1;for(int i=1;i<nums.size();i++){ if(nums[i]>nums[i-1])dp[i]=max(dp[i],dp[i-1]+1);if(result<dp[i])result=dp[i];}return result;}
};
718. 最长重复子数组
题目链接
思路
这道题实在是妙，第一次写真的有人可以想出来吗。
思路就不写了，看图自然能秒懂：
代码实现
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {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;}if(dp[i][j]>result)result=dp[i][j];}} return result;}
};