代码随想录算法训练营day53 | 1143.最长公共子序列，1035.不相交的线，53. 最大子序和

1143.最长公共子序列

• 这道题与#718区别在于这里不要求是连续的了，但要有相对顺序，即："ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
• 与#718类似，在定义dp数组的时候依然可以按照题解的定义方式，即dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。但是也像在#718有的疑问一样，定义并不直观，那么就按照长度为[0, i]的字符串text1和长度为[0, j]的字符串text2来定义，这样就需要初始化dp数组的第一行和第一列。
• 具体代码参考#718第三种解法来写。。。

1035.不相交的线

• 仔细阅读题目发现：直线不能相交，这就是说明在字符串nums1中找到一个与字符串nums2相同的子序列，且这个子序列不能改变相对顺序。只要相对顺序不改变，链接相同数字的直线就不会相交。
• 本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
• 这就与#1143一模一样了
• #718，#1143和#1035一起整理复习！！！

53. 最大子序和

五部曲：

1. 确定dp数组以及下标的含义：dp[i]：包括下标i之前的最大连续子序列和为dp[i]。
2. 确定递推公式：dp[i] = max(dp[i - 1] + nums[i], nums[i]); 

   因为dp[i]只有两个方向可以推出来：

   1. dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
   2. nums[i]，即：从头开始计算当前连续子序列和
3. dp数组如何初始化：从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。dp[0] = nums[0]
4. 确定遍历顺序：递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
5. 打印检查