代码随想录算法训练营第四十四天|动态规划part11

1143.最长公共子序列

题目链接：1143. 最长公共子序列 - 力扣（LeetCode）

文章讲解:代码随想录

思路：

其实就是求两个字符串的最长公共子序列的长度

与公共子数组的区别是可以不连续 ，顺序对就可以

状态转移方程不一样

定义dp[i][j]表示text1的0到i-1与text2的0到j-1的最长公共子序列的长度

text1[i-1]==text2[j-1] dp[i][j]=dp[i-1][j-1]+1

否则等于max（dp[i-1][j],dp[i][j-1]）

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

53. 最大子序和
 

题目链接：53. 最大子数组和 - 力扣（LeetCode）

文章讲解：代码随想录

思路：

由于求子数组 要求连续的 可以设置一个计数器，计数器小于0就重置，

然后记录计数器的最大值

class Solution {
public:int maxSubArray(vector<int>& nums) {int count=0;int ans=nums[0];bool isPositive=false;int x=-INT_MAX;for(int i=0;i<nums.size();i++){      //考虑都是负数的情况if(nums[i]>0)isPositive=true;x=max(x,nums[i]);}if(!isPositive)return x;for(int i=0;i<nums.size();i++){count+=nums[i];if(count<0){count=0;}else{ans=max(ans,count);}}return ans;}
};