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

1143.最长公共子序列
题目链接：1143.最长公共子序列
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰最长公共子序列
日期：2024-10-17

想法：这里的子序列不要求连续了，dp[i][j]要表示为在text1[0, i - 1]和text2[0, j - 1]的范围里，最长的公共子序列长度，-1同样是为了初始化方便，如果text1[i - 1]， text2[j - 1]相等，直接在前一个状态dp[i - 1][j - 1]加1就行，不等的话，就要看是text1减一个长度时的最长公共子序列长还是text2的，即dp[i - 1][j], dp[i][j - 1];
Java代码如下：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();

        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for(int i = 1; i <= text1.length(); i++) {
            for(int j = 1; j <= text2.length(); j++) {
                if(char1[i - 1] == char2[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]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

1035.不相交的线
题目链接：1035.不相交的线
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰不相交的线
日期：2024-10-17

想法：跟上面思路一摸一样。
Java代码如下：

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        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]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}

53. 最大子序和
题目链接：53. 最大子序和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰最大子序和
日期：2024-10-17

想法：关键在于递推公式dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])，本质跟贪心思路一样，dp[i - 1]为负就dp[i]重置为nums[i]
Java代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

392.判断子序列
题目链接：392.判断子序列
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰判断子序列
日期：2024-10-17

想法：跟最长公共子序列的区别在于，字串s必须全部是t的字串，所以当s1[i - 1] ！= t1[j - 1]时s并不能呢再回去了即dp[i - 1][j]是不能要的。最后加个判断条件。
Java代码如下：

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() > t.length()) return false;
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 1; j <= t.length(); j++) {
                if(s1[i - 1] == t1[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        if(dp[s.length()][t.length()] == s.length()) return true;
        return false;
    }
}