【算法刷题day53】Leetcode：1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和

本文主要是介绍【算法刷题day53】Leetcode：1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- Leetcode 1143. 最长公共子序列
- - 解题思路
  - 代码
  - 总结
- Leetcode 1035. 不相交的线
- - 解题思路
  - 代码
  - 总结
- Leetcode 53. 最大子数组和
- - 解题思路
  - 代码
  - 总结

草稿图网站
java的Deque

Leetcode 1143. 最长公共子序列

题目：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

解题思路

和上一题的区别是，不初始化0，如果没匹配到就变为左边数

代码

class Solution {public int longestCommonSubsequence(String text1, String text2) {int res = 0;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 (text1.charAt(i-1) == text2.charAt(j-1))dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);res = Math.max(res, dp[i][j]);}}return res;}
}//滚动数组
class Solution {public int longestCommonSubsequence(String text1, String text2) {int res = 0;int []dp = new int[text2.length()+1];for (int i = 1; i <= text1.length(); i++) {for (int j = text2.length(); j > 0; j--) {if (text1.charAt(i-1) == text2.charAt(j-1))dp[j] = dp[j-1] + 1;elsedp[j] = Math.max(dp[j], dp[j-1]);res = Math.max(res, dp[j]);}}return res;}
}

总结

暂无

Leetcode 1035. 不相交的线

题目：1035. 不相交的线
解析：代码随想录解析

解题思路

上秒那题包了个马甲

代码

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int res = 0;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;elsedp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);res = Math.max(res, dp[i][j]);}}return res;}
}

总结

暂无

Leetcode 53. 最大子数组和

题目：53. 最大子数组和
解析：代码随想录解析

解题思路

dp数组的含义是到这位置的最大和是多少

代码

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