本文主要是介绍Day53| Leetcode 1143. 最长公共子序列 Leetcode 1035. 不相交的线 Leetcode 53. 最大子数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode 1143. 最长公共子序列
题目链接 1143 最长公共子序列
本题目介于上个题目是多了不连续的情况，所以我们就要考虑两个单个字符串不相等的情况，这个地方还是比较难想的，下面上代码：
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));for(int i=1;i<=text1.size();i++){for(int j=1;j<=text2.size();j++){if(text1[i-1] == text2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}return dp[text1.size()][text2.size()];}
};Leetcode 1035. 不相交的线
题目链接 1035 不相交的线
本题目和上面的题目一摸一样，直接上代码：
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,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;}else{dp[i][j] = max(dp[i][j-1],dp[i-1][j]);}}}return dp[nums1.size()][nums2.size()];}
};题目链接 53 最大子数组和
主要是注意递推公式：
dp[i]只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
下面上代码：
class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size() == 0){return 0;}vector<int> dp(nums.size(),0);dp[0] = nums[0];int result = nums[0];for(int i=1;i<nums.size();i++){dp[i] = max(dp[i-1]+nums[i],nums[i]);if(result<dp[i]){result = dp[i];}}return result;}
};补
这篇关于Day53| Leetcode 1143. 最长公共子序列 Leetcode 1035. 不相交的线 Leetcode 53. 最大子数组和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
