Scala解释中的Kadane算法

Question

我对学习如何用foldLeft函数在scala中实现Kadane（最大子数组和）算法感兴趣。我在堆栈溢出中运行了这个示例，但我不确定我是否理解该算法的确切功能。这就是算法的样子：

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

{}中包含的内容是否是需要应用于每个元素的lambda函数？还有，这行maxEndingHere->(maxEndingHere max maxSoFar)到底做什么？为什么括号里的括号用空格隔开？我很感激任何帮助，如果我的问题让人觉得太无知，我很抱歉，但我对Scala是新手

Answer 1

首先，您需要了解什么是foldleft。这个函数的含义是通过传递组合操作和初始元素，将集合折叠为单个值：

// Think of applying op(op(op(…), z) from left to right:
def foldLeft[B](z: B)(op: (B, A) ⇒ B): B

现在，让我们看看foldleft中发生了什么。首先，传递0->0。这意味着初始元素的类型b是一个元组(Int,Int)，其值为(0,0)。

其次，开头的方括号定义了一个函数。在scala中，可以用花括号传递它。因此，该函数需要(B，A)参数。在本例中，B类型是一个元组(Int，Int)，而A类型是数组元素的类型，即Int。

someArray.foldLeft(0 -> 0) {
  (tuple: (Int, Int), element: Int) => //the body
}

val maxEndingHere = 0 max maxUpToHere + n
maxEndingHere -> (maxEndingHere max maxSoFar)