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

LeetCode 1143.最长公共子序列

题目链接：https://leetcode.cn/problems/longest-common-subsequence/description/
文章链接：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

思路

 * dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]* 主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同* 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;* 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。* 即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

public int longestCommonSubsequence(String text1, String text2) {int len1 = text1.length();int len2 = text2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {char t1 = text1.charAt(i);for (int j = 1; j <= len2; j++) {char t2 = text2.charAt(j);if (t1 == t2)dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[len1][len2];}

LeetCode 1035.不相交的线

题目链接：https://leetcode.cn/problems/uncrossed-lines/description/
文章链接：https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

本题其实就是求最长公共子序列

 public int maxUncrossedLines(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[][] dp = new int[len1+1][len2+1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; 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[len1][len2];}

LeetCode 53. 最大子序和

题目链接：https://leetcode.cn/problems/maximum-subarray/description/
文章链接：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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

 * dp[i]表示以nums[i]为结尾的最大子数组的和* 那么对于第i个元素，如果选择加入前面最大子数组的和，那么dp[i] = dp[i-1] + nums[i]* 也可以第i个元素不加入前面子序列，那么就从nums[i]开始重新加，则dp[i] = nums[i]

public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int res = dp[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;}

LeetCode 392.判断子序列

题目链接：https://leetcode.cn/problems/maximum-subarray/description/
文章链接：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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

本题思路和1143.最长公共子序列类似，其实就是求两个字符串的最长公共子序列是否等于其中比较短的字符串

public boolean isSubsequence(String s, String t) {int len1 = s.length();int len2 = t.length();// dp[i][j]表示s串中以第i-1个元素为结尾的子串和t串中以第j-1个元素为结尾的子串的最大公共子序列长度int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1 ; i++) {char si = s.charAt(i - 1);for (int j = 1; j <= len2 ; j++) {char tj = t.charAt(j - 1);if (si == tj) {dp[i][j] = dp[i-1][j-1] + 1;}elsedp[i][j] = dp[i][j-1];}}if (dp[len1][len2] == len1) {return true;}elsereturn false;}