算法训练（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;
    }
};