Scala中的Kadane算法

Question

有没有人在功能样式中完成Kadane算法的Scala实现？

Answer 1

那这个呢:

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

Answer 2

我更喜欢扫描解决方案的折叠解决方案 - 尽管后者确实很优雅.无论如何,

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