代码随想录算法训练营第五十三天|1143.最长公共子序列、1035.不相交的线、718. 最大子序和

代码随想录算法训练营第五十三天|1143.最长公共子序列、1035.不相交的线、718. 最大子序和

最长公共子序列

1143.最长公共子序列
文章讲解：https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
题目链接：https://leetcode.cn/problems/longest-common-subsequence/
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ/

自己看到题目的第一想法

和最长重复子数组的处理逻辑一样。dp[i][j]定义为0到i-1，0到j-1的最长公共子序列。

看完代码随想录之后的想法

这里的递推公式没有想明白，递推公式的第一个判断，nums[i-1]==nums[j-1]和最长重复子数组一样，都取dp[i][j] = dp[i-1][j-1] + 1。
但是当nums[i-1]!=nums[j-1]时，则取dp[i-1][j],dp[i][j-1]的最大值，dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); 如给定 a b c d e；a c e；此时比到 abc和ace，发现c和e不相等，则取 abc和ac以及ab和ace的值的最大值。
这里的初始化值和最长重复子数组一样。

自己实现过程中遇到哪些困难

理解了思路，然后按照思路些代码还是简单的。

public int longestCommonSubsequence(String text1, String text2) {
    char[] text1Array = text1.toCharArray();
    char[] text2Array = text2.toCharArray();
    // 定义dp数组，2层循环，dp[i][j]，以i为结尾的text1Array和以j为结尾的text2Array组成的最大公共子序列长度
    // 确定推导公式，前后有无递推 如果 text1Array[i] == text2Array[j]，不是前一个相等了
    int[][] dp = new int[text1Array.length + 1][text2Array.length + 1];
// dp数组定义 dp[i][j]：用nums1的i-1位置为结尾以及nums2的j-1为结尾的最长子数组长度
int result = 0;
for(int i = 1; i <= text1Array.length; i++){
    for(int j = 1; j <= text2Array.length; j++){
        // 推导公式，如果每个数字的位数都相等，则长度加一
        if(text1Array[i - 1] == text2Array[j - 1]){
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }else{
            dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
        }
        result = Math.max(dp[i][j],result);
    }
}
return result;
}

不相交的线

1035.不相交的线
文章讲解：https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
题目链接：https://leetcode.cn/problems/uncrossed-lines/
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP/

自己看到题目的第一想法

// 不相交的线，满足顺序，但是可以不连续，题目处理的方法和最长公共子序列一致。
代码实现：

public int maxUncrossedLines(int[] nums1, int[] nums2) {
    // 不相交的线，满足顺序，但是可以不连续
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    int result = Integer.MIN_VALUE;
    for(int i = 1; i <= nums1.length; i++){
        for(int j = 1; j <= nums2.length; j++){
            if(nums1[i - 1] == nums2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
            }
            result = Math.max(result,dp[i][j]);
        }
    }
    return result;
}

看完代码随想录之后的想法

思路：
绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

自己实现过程中遇到哪些困难

还是要理解题目中的类似之处。

最大子序和

53. 最大子序和
文章讲解：https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
题目链接：https://leetcode.cn/problems/maximum-subarray/
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5/

自己看到题目的第一想法

dp数组定义：
dp[i]：以i结尾的0-i最大子序和。
递推公式：dp[i-1] >= 0 则dp[i] = dp[i - 1] + nums[i] 否则dp[i] = nums[i]
初始化值：dp[0] = nums[0];

看完代码随想录之后的想法

整体逻辑一样，将dp的取值直接使用Math.max(dp[i - 1] + nums[i], nums[i]);
也是将result的值初始化成了dp[0]；

自己实现过程中遇到哪些困难

1. 边界条件处理没做好。
2. 第0位置的dp状态最大值取值遗漏了。

public int maxSubArray(int[] nums) {
   // 动态规划实现
   // dp数组定义：dp[i]：取0-i时的最大和的连续子数组
   // 确定递推，dp[i-1] >= 0 则dp[i] = dp[i - 1] + nums[i] 否则dp[i] = nums[i]
   // 初始化值，dp[0] = nums[0];
   int[] dp = new int[nums.length];
   dp[0] = nums[0];
   if(nums.length == 1)return nums[0];
   int result = dp[0];
   for(int i = 1; i < nums.length; i++){
       if(dp[i-1] >= 0){
           dp[i] = dp[i - 1] + nums[i];
       }else{
           dp[i] = nums[i];
       }
       result = Math.max(result,dp[i]);
   }
   return result;
}

今日收获&学习时长

1143.最长公共子序列、1035.不相交的线、718. 最大子序和
前面两道题的答案都是一样的，第二道题要理解不相交的概念就是顺序匹配。
第一题、第二题的核心思路是如果当前位相同则取前一位置的最大值+1。不是当前位的话取不相等时的2种状态的最大值 abcde ace，比较到abc和ace时取abc-ac和ab-ace的最大值。

最大子序和的话就是取前一位置+当前位置和当前nums的最大值。