Kadan algorithm in Scala

Question

Does Scala have a functional style implementation of the Kadane algorithm ?

Answer 1

How about this:

numbers.scanLeft(0)((acc, n) => math.max(0, acc + n)).max 

Answer 2

I prefer the folding solution to the scanning solution - although, of course, this is elegance for the latter. Anyway,

 numbers.foldLeft(0 -> 0) { case ((maxUpToHere, maxSoFar), n) => val maxEndingHere = 0 max maxUpToHere + n maxEndingHere -> (maxEndingHere max maxSoFar) }._2 

Answer 3

The following code returns the start and end indices, as well as the sum:

 import scala.math.Numeric.Implicits.infixNumericOps import scala.math.Ordering.Implicits.infixOrderingOps case class Sub[T: Numeric](start: Index, end: Index, sum: T) def maxSubSeq[T](arr: collection.IndexedSeq[T])(implicit n: Numeric[T]) = arr .view .zipWithIndex .scanLeft(Sub(-1, -1, n.zero)) { case (p, (x, i)) if p.sum > n.zero => Sub(p.start, i, p.sum + x) case (_, (x, i)) => Sub(i, i, x) } .drop(1) .maxByOption(_.sum)