Алгоритм Кадане в Scala

Question

У кого-нибудь есть реализация Scala алгоритма Кадане , выполненная в функциональном стиле?

Answer 1

Что по этому поводу:

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

Answer 2

Я предпочитаю складывающееся решение сканирующему, хотя у последнего, безусловно, есть элегантность. Во всяком случае,

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

Answer 3

Следующий код возвращает начальный и конечный индексы, а также сумму:

import scala.math.Numeric.Implicits.infixNumericOps
import scala.math.Ordering.Implicits.infixOrderingOps

case class Sub[T: Numeric](start: Index, end: Index, sum: T)

def maxSubSeq[T](arr: collection.IndexedSeq[T])(implicit n: Numeric[T]) =
  arr
    .view
    .zipWithIndex
    .scanLeft(Sub(-1, -1, n.zero)) {
      case (p, (x, i)) if p.sum > n.zero => Sub(p.start, i, p.sum + x)
      case (_, (x, i))                   => Sub(i, i, x)
    }
    .drop(1)
    .maxByOption(_.sum)