static<E> int lcs (E [] xs, E [] ys) { int a [][] = new int [xs.length][ys.length]; // a[i][j] = lcs (xs [0 .. i], ys [0 .. j]) for (int i=0; i < xs.length; i++) { for (int j=0; j < ys.length; j++) { int diag = ( xs[i].equals (ys[j]) ) ? 1 : 0; a[i][j] = Math.max ( diag + get (a, i-1, j-1), Math.max (get (a, i-1, j ), get (a, i , j-1))); } } return get (a, xs.length-1, ys.length-1); } static int get (int [][] a, int i, int j) { return ((i < 0) || (j < 0)) ? 0 : a[i][j]; }