代码随想Day53 | 1143.最长公共子序列、1035.不相交的线、53. 最大子序和
2024-01-01 06:53:30
1143.最长公共子序列?
本题和?718.?最长重复子数组?的区别就是本题不要求连续,所以在两个字符不相等的时候,逻辑不相同,当不相同的时候,需要找到dp[i-1][j]和dp[i][j-1]之间的最大值,因为不相等的时候需要找出退而求上一个状态的两个值的最大,这样才能得到最长公共子序列数,其他的思路都和重复子数组相同,不再详细赘述。
详细代码如下:
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//和公共重复子数组相似
if(text1.empty()||text2.empty()) return 0;
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][j-1],dp[i-1][j]);
}
}
return dp[text1.size()][text2.size()];
}
};
1035.不相交的线?
其实本题和?1143.最长公共子序列?是一模一样的,不相交的线最多有几根,其实就是不改变相对顺序,最长的重复子序列和,和1143相同,不再赘述,详细代码如下:
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
if(nums1.empty()||nums2.empty()) return 0;
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来做一遍?
dp[i]:以i为结尾的子数组的最大和
递推:
两种可能:1.dp[i-1]小于0,说明前面都是副作用,dp[i]=num[i-1];2. dp[i-1]大于0,则dp[i]=dp[i-1]+nums[i-1];两者求最大
初始化:dp[0]=nums[0];
遍历顺序:从前到后
详细代码:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//dp[i]以i索引结尾的子数组的最大和
if(nums.size()==0) return 0;
vector<int>dp(nums.size(),0);
int res =nums[0];
dp[0]=nums[0];
for(int i=1;i<nums.size();i++)
{
dp[i]=max(dp[i-1]+nums[i],nums[i]);
res=max(res,dp[i]);
}
return res;
}
};
文章来源:https://blog.csdn.net/juantingliu_01/article/details/135320865
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!