LIS Scala

def LIS(x: Array[Int]): Array[Int] = {
  val n = x.length
  val p = Array.ofDim[Int](n)
  val m = Array.ofDim[Int](n + 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 n) {
    val newLow = binarySeach(i)
    p(i) = m(newLow - 1)
    m(newLow) = i

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

  val s = Array.ofDim[Int](l)
  var k = m(l)
  for (i <- (l - 1) to 0 by -1) {
    s(i) = x(k)
    k = p(k)
  }
  s
}