Reputation: 1293
Does anyone have a Scala implementation of Kadane's algorithm done in a functional style?
Edit Note: The definition on the link has changed in a way that invalidated answers to this question -- which goes to show why questions (and answers) should be self-contained instead of relying on external links. Here's the original definition:
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
Upvotes: 11
Views: 1390
Reputation: 3722
What about this, if an empty subarray is allowed or the input array cannot be all negative:
numbers.scanLeft(0)((acc, n) => math.max(0, acc + n)).max
Or, failing the conditions above this (which assumes the input is non-empty):
numbers.tail.scanLeft(numbers.head)((acc, n) => (acc + n).max(n)).max
Upvotes: 19
Reputation: 4310
The following code returns the start and end index 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)
Upvotes: 1
Reputation: 297320
I prefer the folding solution to the scan solution -- though there's certainly elegance to the latter. Anyway,
numbers.foldLeft(0 -> 0) {
case ((maxUpToHere, maxSoFar), n) =>
val maxEndingHere = 0 max maxUpToHere + n
maxEndingHere -> (maxEndingHere max maxSoFar)
}._2
Upvotes: 6