We write the integers of A and B (in the order they are given) on two separate horizontal lines.
Now, we may draw a straight line connecting two numbers A[i] and B[j] as long as A[i] == B[j], and the line we draw does not intersect any other connecting (non-horizontal) line.
Return the maximum number of connecting lines we can draw in this way.
class Solution { public int maxUncrossedLines(int[] A, int[] B) { int n = A.length; int m = B.length; int[][] f = new int[n][m]; for(int i=0;i<n;i++){ if (A[i]==B[0]){ f[i][0] = 1; }else if(i>0){ f[i][0] = f[i-1][0]; } } for(int i=0;i<m;i++){ if (A[0]==B[i]){ f[0][i] = 1; }else if(i>0){ f[0][i] = f[0][i-1]; } } for(int i=1;i<n;i++) for (int j=1;j<m;j++){ if (A[i]==B[j]){ f[i][j] = f[i-1][j-1] +1; }else{ f[i][j] = max(f[i-1][j],f[i][j-1]); } } return f[n-1][m-1]; } private int max(int a,int b){ if (a>b){ return a; } return b; } }
近期评论