33 lines
1.2 KiB
Scala
33 lines
1.2 KiB
Scala
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) // all increasing combinations
|
|
|
|
val all = (1 to l.length)
|
|
.flatMap(i => increasing(l take i takeRight 1, l.drop(i + 1)))
|
|
.sortBy(-_.length)
|
|
all.takeWhile(_.length == all.head.length) // longest of all increasing combinations
|
|
}
|
|
|
|
def asInts(s: String): Array[Int] = s split "," map (_.toInt)
|
|
|
|
assert(tests forall {
|
|
case (given, expect) =>
|
|
val allLongests: Seq[Array[Int]] = lis(asInts(given))
|
|
println(
|
|
s"$given has ${allLongests.length} longest increasing subsequences, e.g. ${
|
|
allLongests.last.mkString(",")}")
|
|
allLongests.forall(lis => expect.contains(lis.mkString(",")))
|
|
})
|
|
}
|