Scala 解释中的 Kadane 算法

Question

我有兴趣学习如何使用 foldLeft 函数在 Scala 中实现 Kadane（最大子数组和）算法。我运行通过 this 关于堆栈溢出的示例，但是我不确定我是否理解该算法的确切作用。算法是这样的：

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

{} 中包含的内容是否需要应用于每个元素的 lambda 函数？还有这条线到底做了什么maxEndingHere -> (maxEndingHere max maxSoFar)？为什么括号中的括号之间用space隔开？感谢任何帮助，如果我的问题太无知，我很抱歉，但我是 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 是数组元素的类型，即 [=23] =].

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

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)

记住，我们的函数应该 return 下一个 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

Scala 解释中的 Kadane 算法

Kadane algorithm in Scala explanation

scala

data-structures

sub-array

foldleft

kadanes-algorithm