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是值为(0, 0)的元组(Int, Int)。

其次，左括号定义一个函数。在 scala 中，您可以使用大括号传递它。因此，该函数需要(B, A)参数，在我们的例子中，B类型是元组(Int, Int)，而A类型是 Array 元素的类型，Int。

因此，当您可以像这样翻译代码时：

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

现在，在 Scala 中，您可以通过应用提供的模式来创建带有case关键字的部分函数。在我们的例子中，模式通过将变量maxUpToHere和maxSoFar绑定到元组元素并将n绑定到数组的元素来匹配提供的参数。

因此，该函数将从数组中获取每个元素，使用提供的元组应用它并将其传递给下一个应用程序，直到数组被完全处理。现在，让我们看看函数体中发生了什么：

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

请记住，我们的函数应该返回下一个B以申请使用数组中的元素进行调用。在我们的例子中，B是一个元组。因此，这个想法是将序列的整体最大值和局部最大值存储在元组中。

maxEndingHere取0与数组n的当前元素的先前计算之和之间的max。如果当前元素为负数，它将减少最大序列，从而在最大比较结果上产生0，从而重置累积值。

然后我们只需使用序列maxEndingHere的新计算总和以及当前值与到目前为止计算的值之间的最大值(因此得名maxSoFar)创建新的元组。

最后，我们只需通过调用._2来获取计算元组的第二个值。

Answer 2

{}

lambda 函数将应用于数组中的每个元素

maxEndingHere -> (maxEndingHere max maxSoFar)

它将 maxUpToHere 设置为 maxEndingHere，并将 maxSoFar 设置为 maxEndingHere 和 maxSoFar 之间的最大值结果，以便下一次迭代

所以要干运行代码：对于下面的数组，代码对数组的每个元素运行如下

someArray: Array[Int] = Array(5, 2, -10, 6, 8)
For element n = 5
maxUptoHere = 0
maxSoFar = 0
n = 5
maxEndingHere = 5
For element n = 2
maxUptoHere = 5
maxSoFar = 5
n = 2
maxEndingHere = 7
For element n = -10
maxUptoHere = 7
maxSoFar = 7
n = -10
maxEndingHere = 0
For element n = 6
maxUptoHere = 0
maxSoFar = 7
n = 6
maxEndingHere = 6
For element n = 8
maxUptoHere = 6
maxSoFar = 7
n = 8
maxEndingHere = 14
res15: Int = 14