1. 最长重复子数组
算法思路
1. 最大公共子数组就是最大公共连续子序列；
2. 不同于最长连续递增子序列那道题，此题是两个数组相互比较，所以将dp数组设定为二维数组，定义为分别以nums1[i]和nums2[j]结尾的两个子数组的最大公共子数组的长度。
注意点
虽然已经初始化，但是遍历要从i=0和j=0开始，不然0的情况进入不了循环，就不能跟result比较，导致最后result为0，结果错误。
代码
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length][nums2.length];for(int i = 0; i<nums1.length; i++){if(nums1[i] == nums2[0]) dp[i][0] = 1;}for(int j = 0; j<nums2.length; j++){if(nums1[0] == nums2[j]) dp[0][j] = 1;}int result = 0;for(int i = 0; i<nums1.length; i++){for(int j = 0; j<nums2.length; j++){if(nums1[i] == nums2[j] && i>0 && j>0){dp[i][j] = dp[i-1][j-1]+1;}result = Math.max(result, dp[i][j]);} }return result; }
}
2. 最长公共子序列
算法思路
这题主要难在dp数组的定义：dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]，这样就可以将没有意义的dp[i]0]和dp[0][j]全部赋值为0.
注意点
1. 为了避免初始化的复杂，将dp[i][j]定义为：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]；
2. dp[i][j]定义为长度为 i 和 j 的字符串，这题就没有通过，我不知道为什么；
3. 这题居然不用再求一遍最大值dp[i][j]，是因为数组越长，公共子序列当然就越长了。
代码
class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] c1 = text1.toCharArray();char[] c2 = text2.toCharArray();int[][] dp = new int[c1.length+1][c2.length+1];int result = 0;for(int i = 1; i<=c1.length; i++){for(int j = 1; j<=c2.length; j++){if(c1[i-1] == c2[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; }
}
3. 不相交的线
算法思路
1. 不相交的意思就是数组里的元素相对顺序不改变；
2. 做法和上题求最长公共子序列几乎完全一样。
注意点
代码
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];}
}
4. 最长连续递增序列
算法思路
递推公式包括两种情况：1. 从前面继续累加；2. 从当前位置重新累加。
注意点
result的初始化不能为0！！！而是nums[0]，否则遇到全是负数的情况，会出现错误。
代码
class Solution {public int maxSubArray(int[] nums) {if(nums.length == 0) return 0;int[] dp = new int[nums.length];dp[0] = nums[0];int result = nums[0];for(int i = 1; i<nums.length; i++){dp[i] = Math.max(dp[i-1]+nums[i], nums[i]); result = Math.max(dp[i], result);}return result;}
}
5. 判断子序列
算法思路
1. 本题相当于求最大公共子序列，若最大公共子序列长度等于 s 的长度，则 s 是 t 的子序列。
注意点
因为 s 里面不能删元素，而 t 里面可以删元素，所以不同于最大公共子序列，这里的dp[i][j] = dp[i][j-1]。
代码
class Solution {public boolean isSubsequence(String s, String t) {char[] c1 = s.toCharArray();char[] c2 = t.toCharArray();int[][] dp = new int[c1.length+1][c2.length+1];for(int i = 1; i<=c1.length; i++){for(int j = 1; j<=c2.length; j++){if(c1[i-1] == c2[j-1]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = dp[i][j-1]; }}if(dp[c1.length][c2.length] == c1.length) return true;return false;}
}
)
