10

Kadane のアルゴリズムを関数型スタイルでScala に実装した人はいますか?

編集注:リンクの定義は、この質問への回答を無効にする方法で変更されました。これは、外部リンクに依存するのではなく、質問 (および回答) を自己完結型にする必要がある理由を示しています。元の定義は次のとおりです。

コンピューター サイエンスでは、最大部分配列問題は、数値の 1 次元配列 (少なくとも 1 つの正の数を含む) 内で合計が最大になる連続した部分配列を見つけるタスクです。たとえば、一連の値 -2, 1, -3, 4, -1, 2, 1, -5, 4; 合計が最大の連続する部分配列は 4, −1, 2, 1 で、合計は 6 です。

4

3 に答える 3

17

空の部分配列が許可されている場合、または入力配列がすべて負になることができない場合はどうなりますか。

numbers.scanLeft(0)((acc, n) => math.max(0, acc + n)).max

または、上記の条件に失敗した場合 (入力が空でないことを前提としています):

numbers.tail.scanLeft(numbers.head)((acc, n) => (acc + n).max(n)).max
于 2012-01-28T01:20:53.080 に答える
6

私はスキャンソリューションよりもフォールディングソリューションの方が好きですが、スキャンソリューションには確かに優雅さがあります。ともかく、

numbers.foldLeft(0 -> 0) {
  case ((maxUpToHere, maxSoFar), n) =>
    val maxEndingHere = 0 max maxUpToHere + n
    maxEndingHere -> (maxEndingHere max maxSoFar)
}._2
于 2012-01-29T00:58:14.210 に答える