scala - 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)