租空间网站,长沙建设教育网站,ai效果图网站,天津营销网站建设公司排名文章目录 300.最长递增子序列思路代码实现 674. 最长连续递增序列思路代码实现 718. 最长重复子数组思路代码实现 300.最长递增子序列
题目链接
思路
单个字符都是一个长为1的子序列#xff0c;直接初始化dp为1。先固定一个元素位置i#xff0c;判断0-i范围内到i的最长子序… 文章目录 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(vectorint nums) {vectorint dp(nums.size(),1);int result1;for(int i1;inums.size();i){ for(int j0;ji;j){if(nums[i]nums[j])dp[i]max(dp[i],dp[j]1);}if(resultdp[i])resultdp[i];}return result;}
};674. 最长连续递增序列
题目链接
思路
思路和上一题差不多不过上一题范围比较广0-i范围内可以跳跃性构成子序列但这道题必须相邻所以判断条件改为nums[i]nums[i-1]即可。
代码实现
class Solution {
public:int findLengthOfLCIS(vectorint nums) {vectorint dp(nums.size(),1);int result1;for(int i1;inums.size();i){ if(nums[i]nums[i-1])dp[i]max(dp[i],dp[i-1]1);if(resultdp[i])resultdp[i];}return result;}
};718. 最长重复子数组
题目链接
思路
这道题实在是妙第一次写真的有人可以想出来吗。 思路就不写了看图自然能秒懂
代码实现
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size()1,vectorint(nums2.size()1,0));int result0;for(int i1;inums1.size();i){ for(int j1;jnums2.size();j){ if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}if(dp[i][j]result)resultdp[i][j];}} return result;}
};
