代码随想录算法训练营day43

1.最长递增子序列

1.1 题目

. - 力扣（LeetCode）

1.2 题解

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size()==1)return 1;//定义dp数组，dp[i]表示以nums[i]结尾的最长递增子序列的长度vector<int> dp(nums.size(), 1);//确定递推逻辑//if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);//初始化，都初始化为1//开始遍历int result = 0;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 (dp[i] > result)result = dp[i];}return result;}
};

2.最长连续递增序列

2.1 题目

. - 力扣（LeetCode）

2.2 题解

class Solution {
public:int findLengthOfLCIS(vector<int>& nums){int len = nums.size();if (len <= 0)return len;//确定dp数组，dp[i]表示以nums[i]结尾的最长连续递增子序列vector<int> dp(len,1);//确定递推逻辑//遍历int result = 0;for (int i = 0; i < len; i++){if (i > 0){if (nums[i] > nums[i - 1])dp[i] = dp[i - 1] + 1;}result = max(result, dp[i]);}return result;}
};

3.最长重复子数组

3.1 题目

. - 力扣（LeetCode）

3.2 题解

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {//确定dp数组，dp[i][j]表示以nums1[i-1]为结尾的A和nums2[j-1]结尾的B，最长重复子数组长度为dp[i][j]vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));//确定递推公式//if (nums1[i - 1] == nums2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;//初始化//遍历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;}
};