LCS -- bottom-up (quadratisch)

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];
}