Scala code

def longuestIncreasingSubsequence(x: Array[Int]): Array[Int] = {
  val p = Array.ofDim[Int](x.length)
  val m = Array.ofDim[Int](x.length + 1)
  var l = 0

  def binarySeach(i: Int): Int = {
    var lo = 1
    var hi = l

    while (lo <= hi) {
      val mid = (lo + hi) / 2

      if (x(m(mid)) < x(i)) {
        lo = mid + 1
      } else {
        hi = mid - 1
      }
    }

    lo
  }

  for (i <- 0 until x.length) {
    val localLow = binarySeach(i)

    p(i) = m(localLow - 1)
    m(localLow) = i

    if (localLow > l) {
      l = localLow
    }
  }

  val lis = Array.ofDim[Int](l)
  var k = m(l)

  for (i <- (l - 1) to 0 by -1) {
    lis(i) = x(k)
    k = p(k)
  }

  lis
}