object LongestIncreasingSubsequence extends App {
  val tests = Map(
    "3,2,6,4,5,1" -> Seq("2,4,5", "3,4,5"),
    "0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15" -> Seq("0,2,6,9,11,15", "0,2,6,9,13,15", "0,4,6,9,13,15", "0,4,6,9,11,15")
  )

  def lis(l: Array[Int]): Seq[Array[Int]] =
    if (l.length < 2) Seq(l)
    else {
      def increasing(done: Array[Int], remaining: Array[Int]): Seq[Array[Int]] =
        if (remaining.isEmpty) Seq(done)
        else
          (if (remaining.head > done.last)
            increasing(done :+ remaining.head, remaining.tail)
          else Nil) ++ increasing(done, remaining.tail)