最长重复子数组（中等）

2020年7月1日

题目来源：力扣

解题

刷了三个月简单题入门了一下，现在开始刷每日一题

这个最长重复子数组，用动态规划的方式比较好做，dp数组每次都记录是否相等，如果相等就在上一个数那里加一。

class Solution { public int findLength(int[] A, int[] B) { int max=0; int alen=A.length; int blen=B.length; int[][] dp=new int[alen+1][blen+1]; for(int i=1;i<=alen;i++){ for(int j=1;j<=blen;j++){ if(A[i-1]==B[j-1]){ dp[i][j]=dp[i-1][j-1]+1; max=Math.max(max,dp[i][j]); } } } return max; } }

DP二维数组改一维数组

由二维数组可知，dp[i][j]=dp[i-1][j-1]+1。那么可以发现这个矩形是斜线递增的，而且每次都只是依赖上一行的数据，那么改写成一维数组，这里要注意，后面的数据是依赖于前面的数据，前面的数据是用来推导后面的数据，所以前面的数据不依赖后面的数据，我们就需要从后面开始对比，以免影响结果。 还有因为是一维数组，所以不相等的要实时刷新为0。

class Solution { public int findLength(int[] A, int[] B) { int max=0; int alen=A.length; int blen=B.length; int[] dp=new int[blen+1]; for(int i=1;i<=alen;i++){ for(int j=blen;j>=1;j--){ if(A[i-1]==B[j-1]){ dp[j]=dp[j-1]+1; max=Math.max(max,dp[j]); } else dp[j]=0; } } return max; } }