【代码训练营】day53 | 1143.最长公共子序列 1035.不相交的线 53. 最大子序和

所用代码 java

最长公告子序列 LeetCode 1143

题目链接：最长公告子序列 LeetCode 1143 - 中等

思路

这个相等于上一题的不连续状态

• dp[i] [j]：以[0, i-1]text1和以[0, j-1]text2 的最长公共子序列的长度为dp[i] [j]
• 递推公式：
  • 相同：if(text1.charAt(i-1) == text2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
  • 不相同：else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
• 初始化：第一行，第一列即i=0，j=0的情况，无实意因为0
• 遍历顺序：先i后j，先j都i都可以
• 打印dp
• 结果：需保留在一个result中，最后一个数不一定是最长的

class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length() + 1][text2.length() + 1];int result = 0;// 初始化 -- dp[i][0]和dp[0][j]无意义初始化为0for (int i = 1; i <= text1.length(); i++) {for (int j = 1; j <= text2.length(); j++) {// 以i-1和j-1结尾的两个字符相等，最大子序列就+1// 不相等话就保留前一个最大的长度if (text1.charAt(i-1) == text2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1] + 1;} else{dp[i][j] = Math.max(dp[i-1][j], dp[i][j- ]);}result = Math.max(result, dp[i][j]);}
//            System.out.println(Arrays.toString(dp[i]));}return result;}
}

总结

本题关键在于我们相等的时候是直接去那个数+1，不相等则保留。

因为我们的dp数组的定义就是如此，abc aac这两个串，b对应第二个a时，前面还有一个a相等，所有对应的状态为1，否则就会漏掉一些需要的状态。

本题还可以用一维数组的方法，但不建议：

关键在于需要一个额外的参数来记录上一列的值，即dp[i-1] [j-1]，想通这一点就好办了

class Solution {public int longestCommonSubsequence(String text1, String text2) {int n1 = text1.length();int n2 = text2.length();// 放在第二个for里面，所有n2+1int[] dp = new int[n2+1];// 0无实意、初始化为0for (int i = 1; i <= n1; i++) {// pre 相当于dp[i-1][j-1]int pre = dp[0];for (int j = 1; j <= n2; j++) {// cur用于更新preint cur = dp[j];if (text1.charAt(i-1) == text2.charAt(j-1)){dp[j] = pre + 1;}else {dp[j] = Math.max(dp[j], dp[j-1]);}pre = cur;}
//            System.out.println("pre = " + pre);System.out.println(Arrays.toString(dp));}return dp[n2];}
}

打印dp：

Your input:"abcde""ace"
Output:3
Expected:3
stdout:[0, 1, 1, 1]  pre = 1[0, 1, 1, 1]  pre = 1[0, 1, 2, 2]  pre = 2[0, 1, 2, 2]  pre = 2[0, 1, 2, 3]  pre = 3

不相交的线 LeetCode 1035

题目链接：不相交的线 LeetCode 1035 - 中等

思路

无。

---

找相同的元素，且要保证顺序，相当于找相同子序列！

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int n1 = nums1.length;int n2 = nums2.length;int[][] dp = new int[n1 + 1][n2 + 1];int result = 0;for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; 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;}
}

总结

这题和上一题是一样的代码，我花了很长时间去想怎样才能保证不相交，结果思路就错了。

重点是要分析出题目的意思，两个数组相同元素连接起来应该是怎样连的我们根本不用关心，我们只用知道相连的元素相当于数组的子序列，这就保证了连线不相交！

最大子序和 LeetCode

题目链接：最大子序和 LeetCode - 中等

思路

本题可用贪心，累计最大和就是和为正数可继续添加，负数则舍去。

• dp[i]：以nums[i]为结尾的的最大联系子序列和为 dp[i]
• 递推公式：dp[i] = max(dp[i-1] + nums[i],dp[i] )
  • 延续前面的子序列和：dp[i-1] + nums[i]
  • 前面不要了，从头计算：dp[i]
• 初始化：dp[0] = nums[0] 按照dp数组意义
• 遍历顺序
• 打印
• 结果：并不一定在结尾的位置

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];// 初始化 - 只有一个数序列和肯定为他自己dp[0] = nums[0];int maxSUm = dp[0]; // 最大的序列和可能不在末尾，需用一个数保存for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);maxSUm = Math.max(maxSUm, dp[i]);}
//        System.out.println(Arrays.toString(dp));return maxSUm;}
}

总结

我们发现本题递推公式只与前一个值有关，所以可以把一维的数组压缩成零维，也就是一个数。

class Solution {public int maxSubArray(int[] nums) {int pre = nums[0]; // 前一次状态的值int maxSum = nums[0];for (int i = 1; i < nums.length; i++) {// 判断：我们只取前一次状态的还是需要加上本次状态的nums[i]pre = Math.max(pre + nums[i], nums[i]);maxSum = Math.max(maxSum, pre);}return maxSum;}
}

压缩空间使我们空间复杂度从O(n)变为了O(1)，极大的提高了运算速度。