1

我有兴趣学习如何使用 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 新手

4

2 回答 2

4

首先，您需要了解是什么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
}

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

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

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

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

取上一次计算与数组当前元素的maxEndingHere中间max值和总和。如果当前元素为负数，它将减少最大序列，从而产生最大比较结果，从而重置累加值。0n0

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

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

于 2019-11-18T12:00:21.790 回答
1 
{}

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
于 2019-11-18T12:18:52.847 回答