代码随想录算法训练营第五十天|LeetCode1143 最长公共子序列、LeetCode1035 不相交的线、LeetCode53 最大子数组和

题1：

指路：1143. 最长公共子序列 - 力扣（LeetCode）

思路与代码：

类似于最长重复子数组，我们依旧定义一个二维数组dp[i][j]，其含义为从0到以i-1结尾的nums1数组和从0到j-1结尾的nums2数组的最长公共子序列的长度。如果nums1中的数和nums2的数相等时dp数组得到一个结果，即为dp[i][j]=dp[i-1][j-1]+1，当两个数组中的数值不相等时，就将行或列后退一位取二者较大值，即为dp[i][j]=max(dp[i-1][j], dp[i][j-1])。相似的，我们将dp数组结尾定义为i-1和j-1，那么这里就可以直接初始化为0。最后返回即可。代码如下：

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()];}
};

题2：

指路：1035. 不相交的线 - 力扣（LeetCode）

思路与代码：

这个题跟上一个题大同小异。代码如下：

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1));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 - 1][j], dp[i][j - 1]);}}}return dp[nums1.size()][nums2.size()];}
};

题3：

指路：53. 最大子数组和 - 力扣（LeetCode）

思路与代码：

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size());dp[0] = nums[0];int sum = dp[0];for (int i = 1; i < nums.size(); i++) {dp[i] = max(dp[i - 1] + nums[i], nums[i]);if (dp[i] > sum) {sum = dp[i];} }return sum;}
};