0

指定された配列の連続したサブ配列から最大合計を与えるスカラ コードを記述しようとしています。たとえば、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

明らかに、命令型の場合と同様に、この計算では入力データに沿って 2 つの値を伝播する必要があります。

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 に答える