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

本文主要是介绍代码随想录算法训练营第五十三天|1143.最长公共子序列、1035.不相交的线、53.最大子数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1143.最长公共子序列

思路：这道题与上一道题的区别就是是否为公共连续的子序列，这道题为非连续的公共子序列相等的最大长度！依然是利用二维数组，但是这个时候要注意区分相等与不相等的情况，对于连续的而言，如果这两个位置不等，那么dp数组的这个位置一定是为0的，（其实这里也可以联系到最后一题，如果不能连续起来，那么dp不动，相当于以该点为起始位置，重新开始，而因为最后一题的为了记录其值，所以以这个地方为起点，要把该值加入进去！），但是对于本道题而言，如果当前节点不相等，那么需要讨论一个问题，此时的位置前面的最长公共子序列长度是多少？要进行更新！

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));int result=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()];}
};

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-1][j],dp[i][j-1]);}}}return dp[nums1.size()][nums2.size()];}
};

53.最大子数组和

动态规划：首先确定dp数组的含义，第i个位置的连续数组和是多少，那么第一种更新的情况肯定是前i-1数组的大小+当前这个位置的大小，另外一种是若前i-1数组的大小为负的，那么加上当前的位置的数，会变得更小，所以此时不如从当前节点重新开始！（最开始的错误思考：递推公式max(dp[i-1],dp[i-1]+nums[i])这个地方明显出现错误了，若dp[i-1]+num[i]比dp[i-1]还小，那么我们压根不可能要第i个数，故不可能连续起来的！）

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