2 A surpassing_problem

2_a_surpassing_problem.scala

package surpassing.problem

object Specification {
  def msc[A: Ordering](xs: List[A]) = (for (z :: zs <- tails(xs)) yield scount(z, zs)).max

  def scount[A](x: A, xs: List[A])(implicit o: Ordering[A]) = {
    import o._
    xs.filter(x < _).length
  }

  def tails[A](xs: List[A]): List[List[A]] = xs match {
    case Nil => Nil
    case x :: xs1 => (x :: xs1) :: tails(xs1)
  }
}

object DivideAndConquerSolution {
  def table[A: Ordering](xs: List[A]): List[(A, Int)] = xs match {
    case x :: Nil => (x, 0) :: Nil
    case y :: ys =>
      val m = xs.length
      val n = m / 2
      val (ys, zs) = xs.splitAt(n)
      join(m - n, table(ys), table(zs))
  }

  def join[A](n: Int, txs: List[(A, Int)], tys: List[(A, Int)])(implicit o: Ordering[A]): List[(A, Int)] = (n, txs, tys) match {
    case (0, _, _) => txs
    case (_, Nil, _) => tys
    case (n, (x, c) :: txs1, (y, d) :: tys1) =>
      import o._
      if (x < y) {
        (x, c + n) :: join(n, txs1, tys)
      } else {
        (y, d) :: join(n - 1, txs, tys1)
      }
  }

  def msc[A: Ordering](xs: List[A]) = table(xs).map(_._2).max
}