有没有人以函数式风格完成Kadane 算法的 Scala 实现?
编辑说明:链接上的定义发生了变化,导致该问题的答案无效——这说明了为什么问题(和答案)应该是独立的,而不是依赖于外部链接。这是原始定义:
在计算机科学中,最大子数组问题是在具有最大和的一维数字数组(包含至少一个正数)中找到连续子数组的任务。例如,对于值序列 -2、1、-3、4、-1、2、1、-5、4;和最大的连续子数组是 4、-1、2、1,总和为 6。
有没有人以函数式风格完成Kadane 算法的 Scala 实现?
编辑说明:链接上的定义发生了变化,导致该问题的答案无效——这说明了为什么问题(和答案)应该是独立的,而不是依赖于外部链接。这是原始定义:
在计算机科学中,最大子数组问题是在具有最大和的一维数字数组(包含至少一个正数)中找到连续子数组的任务。例如,对于值序列 -2、1、-3、4、-1、2、1、-5、4;和最大的连续子数组是 4、-1、2、1,总和为 6。
如果允许空子数组或输入数组不能全为负数,那该怎么办:
numbers.scanLeft(0)((acc, n) => math.max(0, acc + n)).max
或者,不满足上述条件(假设输入非空):
numbers.tail.scanLeft(numbers.head)((acc, n) => (acc + n).max(n)).max
我更喜欢折叠解决方案而不是扫描解决方案——尽管后者肯定很优雅。反正,
numbers.foldLeft(0 -> 0) {
case ((maxUpToHere, maxSoFar), n) =>
val maxEndingHere = 0 max maxUpToHere + n
maxEndingHere -> (maxEndingHere max maxSoFar)
}._2
以下代码返回开始和结束索引以及总和:
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)