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)