Scala 中的 Kadane 算法

Question

有人以函数式的方式实现Kadane算法的Scala吗？

编辑注意：链接上的定义发生了变化，导致该问题的答案无效——这表明了为什么问题（和答案）应该是自包含的，而不是依赖外部链接。以下是最初的定义：

在计算机科学中，最大子阵列问题是在一维数字阵列（至少包含一个正数）中找到求和最大的相邻子阵列的任务。例如，对于值的序列−2、1、−3、4、−1、2、1和−5、4；和最大的邻接子阵列是4，−1，2，1，和为6。

Answer 1

如果允许一个空的子数组，或者输入数组不能全部为负，那该怎么办：

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

或者，如果不满足上述条件（假设输入为非空）：

numbers.tail.scanLeft(numbers.head)((acc, n) => (acc + n).max(n)).max

Answer 2

比起扫描解决方案，我更喜欢折叠解决方案——尽管后者肯定很优雅。不管怎样，

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

Answer 3

以下代码返回开始和结束索引以及总和：

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)