fork download
copy 
  1. object LongestIncreasingSubsequence extends App {
  2.   def longest(l: Array[Int]) = l match {
  3.     case _ if l.length < 2 => Array(l)
  4.     case l =>
  5.       def increasing(done: Array[Int], remaining: Array[Int]): Array[Array[Int]] = remaining match {
  6.         case Array() => Array(done)
  7.         case Array(head, _*) =>
  8.           (if (head > done.last) increasing(done :+ head, remaining.tail) else Array()) ++
  9.           increasing(done, remaining.tail) // all increasing combinations
  10.       }
  11.       val all = (1 to l.length).flatMap(i => increasing(l take i takeRight 1, l.drop(i+1))).sortBy(-_.length)
  12.       all.takeWhile(_.length == all.head.length).toArray // longest from all increasing combinations
  13.   }
  14.  
  15.   val tests = Map(
  16.     "3,2,6,4,5,1" -> Array("2,4,5", "3,4,5"),
  17.     "0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15" -> Array("0,2,6,9,11,15", "0,2,6,9,13,15", "0,4,6,9,13,15", "0,4,6,9,11,15")
  18.   )
  19.   def asInts(s: String): Array[Int] = s split "," map Integer.parseInt
  20.   assert(tests forall {case (given, expect) =>
  21.       val lis = longest(asInts(given))
  22.       println(s"$given has ${lis.size} longest increasing subsequences, e.g. "+lis.last.mkString(","))
  23.       expect contains lis.last.mkString(",")
  24.   })
  25. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/opt/scala/bin/scalac: line 50: /dev/null: Permission denied
spoj: The program compiled successfully, but Main.class was not found.
      Class Main should contain method: def main(args: Array[String]).
stdout
copy 
Standard output is empty
https://ideone.com/AjWduc
language:
Scala (scala 2.12.8)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!