算法训练（leetcode）第三十八天 | 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和、392. 判断子序列

*1143. 最长公共子序列

leetcode题目地址

本题和718. 最长重复子数组相似，只是本题不要求连续，需要记录前面最长的子序列，在此基础上累计长度。

dp[i][j]表示到text1串i-1之前与text2到j-1之前的最长公共子序列的长度。

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

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

1035. 不相交的线

leetcode题目地址

本题和上题完全一致。

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

// c++
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 i,j;for(i=1; i<=nums1.size(); i++){for(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[i-1][j-1];}
};

53. 最大子数组和

leetcode题目地址

dp[i]表示在下标i之前的最大子数组和。这里需要注意题目要求子数组最少包含一个元素，因此不能将子序列和跟0比，而要跟当前元素比，表示从当前位置开始为子数组头。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

392. 判断子序列

leetcode题目地址

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:bool isSubsequence(string s, string t) {if(t.size()<s.size()) return false;int last = 0;for(int i=0; i<s.size(); i++){bool flag = false;for(int j=last; j<t.size(); j++){if(s[i]==t[j]) {flag = true;last = j+1;break;}}if(!flag) return false;}return true;}
};