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; }
};

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;}
};