C++ day53 最长公共子序列 不相交的线 最大子序和

题目1：1143  最长公共子序列

题目链接：最长公共子序列

对题目的理解

返回两个字符串的最长公共子序列的长度，如果不存在公共子序列，返回0，注意返回的是最长公共子序列，与前一天的最后一道题不同的是子序列是可以不连续的

动态规划

动规五部曲

1）dp数组及下标i的含义

dp[i][j]：以[0,i-1]的nums1和以[0,j-1]的nums2的最长公共子序列的长度

2）递推公式

主要是两种情况，1）元素相同；2）元素不同

3）dp数组初始化

dp[i][0]和dp[0][j]  无意义，但是为了递推公式的需要，均初始化为0，其余下标位置处的数值初始化为任意值均可，但是为了方便起见，均初始化为0。

4）遍历顺序

根据递推公式，由左往右推导遍历，从上到下推导遍历。

5）打印dp数组

最终结果在dp[num1.size()][nums2.size()]

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //定义并初始化dp数组
        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-1][j],dp[i][j-1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

• 时间复杂度: O(n * m)，其中 n 和 m 分别为 text1 和 text2 的长度
• 空间复杂度: O(n * m)

题目2：1035  不相交的线

题目链接：不相交的线
对题目的理解

连接数组nums1和nums2中的相同数字代表的点，每条直线不能相交，计算最大连线数

直线不能相交，这就是说明在字符串A中找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，连接相同数字的直线就不会相交。

本题就是套了一层连线的外壳，代码与上一道题一模一样，就是找两个数组中存在的最大相同子序列的长度。

分析过程与上一道题一模一样

代码

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        //定义并初始化dp数组
        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()];
    }
};

• 时间复杂度: O(n * m)
• 空间复杂度: O(n * m)

题目3：53  最大子序和

题目链接：最大子序和

对题目的理解

找出具有最大和的连续子数组（至少包含一个元素），返回最大和，注意子数组是连续的

贪心算法

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小；全局最优：选取最大“连续和”

不断调整最大子序和区间的起始位置，只要连续和还是正数就会对后面的元素起到增大总和的作用。 所以只要连续和为正数就保留。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int count=0;//记录连续和
        int result = INT_MIN;//记录最大连续和
        for(int i=0;i<nums.size();i++){
            count += nums[i];
            if(count>result) result = count;
            if(count<0) count = 0;//连续和为负数，重新计算连续和
        }
        return result;
    }
};

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

动态规划

动规五部曲

1）dp数组及下标i的含义

dp[i]:以nums[i]结尾(包括nums[i])的最大连续子序列的和

2）递推公式

dp[i]可以从两个方向推导出来

1）延续前面的和：dp[i]=dp[i-1]+nums[i]

2）从nums[i]重新计算：dp[i]=nums[i]

dp[i]=max(dp[i-1]+nums[i],nums[i])

3）dp数组初始化

根据递推公式，dp[i]依赖于dp[i-1]   源头是dp[0]，根据dp数组定义，dp[0]=nums[0]

非0下标的dp数组，可以初始化为任意值，因为可以在后续计算中被覆盖，但是为了初始化方便，统一初始为nums[0]

4）遍历顺序

根据递推公式，dp[i]依赖于dp[i-1]，从前往后遍历

for(i=1;i<nums.size();i++)  注意i从1开始遍历

5）打印dp数组

根据dp数组定义，最终结果不一定是dp[nums[i]-1]，应该找每一个i为终点的连续最大子序列，需要把所有结果遍历一遍，求得最大值

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //定义并初始化dp数组
        vector<int> dp(nums.size(),nums[0]);
        int result = INT_MIN;
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            cout<<dp[i]<<endl;
            result = max(result,dp[i]);
        }
        return result;
    }
};

上述代码会出现如下的案例错误

错误的原因在于：result初始化为最小值，而for循环中计算的是dp[1]，就是max(dp[0]+nums[1],nums[1])，是从数组中的第二个元素开始考虑的，如果这样的话，对于只有一个元素的数组根本就没有经过for循环，直接输出了result，所有result不能这样初始化，应该初始化为nums[0]，即初始化为数组的第1个元素值，这样才能在数组只有1个元素的情况下，result考虑到第一个元素。

代码改正如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //定义并初始化dp数组
        vector<int> dp(nums.size(),nums[0]);
        int result = nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            cout<<dp[i]<<endl;
            result = max(result,dp[i]);
        }
        return result;
    }
};

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