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;
}
};1035.不相交的线
题目链接：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,0));
int ans=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]);
}
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;
}
};392.判断子序列
题目链接：392. 判断子序列 - 力扣（LeetCode）
文章讲解：代码随想录
双指针
设置一个计数器，如果相等，计数器+1，最后判断计数器与s的长度是否相等
class Solution {
public:
bool isSubsequence(string s, string t) {
int j=0;
int count=0;
for(int i=0;i<s.size();i++){
for(;j<t.size();j++){
if(s[i]==t[j]){
count++;
j++;
break;
}
}
}
return count==s.size();
}
};注意！！break 后j不加1，需要手动加1；