Problem: The input is a sequence of digits consistent of 0-9. We define "increasing subsequence", when the substring consists of consecutive numbers (NOT including equal). For instance, 0369, 3478, 58. Please write a program (using C, Java, PHP, Ruby or Python) to find the longest increasing subsequence of numbers in the given string.

gistfile1.scala

object IncSeq {
  def main(args: Array[String]) {
    val result = substrLongestIncSeq("333201299823423234")
    println(result) // 0129
  }

  def substrLongestIncSeq(str: String): String = {
    def rec(nums: List[Char], buf: List[Char] = Nil): List[String] =
      nums match {
        case Nil => Nil
        case x :: xs =>
          if (x >= (xs.headOption getOrElse '0'))
            (x :: buf).reverse.mkString :: rec(xs)
          else
            rec(xs, x :: buf)
      }

    val strReg = "^[0-9]+$".r
    str match {
      case strReg() =>
        rec(str.toList).maxBy(_.length)
      case _ => throw new IllegalArgumentException("only numeric char allowed. ([0-9]+)")
    }
  }
}

良く考えたら ListBuffer である必要が無かったので、修正。

コレクションのメソッドに maxBy というまさにピッタリのメソッドが有ったので sortBy + reverse + head をこれに置き換え。

末尾再帰に最適化してないのはご愛嬌ということで。