0

我正在尝试编写 scala 代码，该代码从给定数组的连续子数组中给出最大总和。例如，val arr= Array(-2, -3, 4, -1, -2, 1, 5, -3)。在这个数组中，我需要获得最大的连续子数组和，即 4+(-1)+(-2)+(1)+5 = 7。我编写了以下代码来获得这个结果。

scala> arr.foldLeft(0) { (currsum,newnum) => if((currsum+newnum)<0) 0 else { if(currsum<(currsum+newnum)) (currsum+newnum) else currsum }}
res5: Int = 10

maximum_so_far但与实际结果有偏差，因为随着计数/求和的进行，我无法更新该值。由于我曾经做过这个功能，只有当连续子数组元素的总和大于之前的 max_sum 时foldLeft，是否有可能更新变量？maximum_so_far

参考链接，以更好地理解场景

4

1 回答 1

1

好吧，显然您必须在输入数据中传播两个值以进行此计算，就像在命令式情况下需要做的那样：

arr.foldLeft((0,0)){
  case ((maxSum, curSum), value) => {
    val newSum = Math.max(0, curSum + value)
    (Math.max(maxSum, newSum), newSum)  
  }
}._1

另一种方法是计算中间结果（如果需要，可以懒惰地计算），然后选择最大值：

arr.toIterator.scanLeft(0){
  case (curSum, value) =>
    Math.max(0, curSum + value)
}.max
于 2016-02-13T12:32:12.357 回答