Scala中的Kadane算法
Scala中的Kadane算法
提问于 2012-01-28 00:22:46
有谁有用函数样式实现卡达内算法的Scala实现吗？
编辑注意:链接上的定义发生了变化，使这个问题的答案失效--这说明了为什么问题(和答案)应该是独立的--而不是依赖外部链接。这是最初的定义：
在计算机科学中，最大子阵问题是在具有最大和的一维数数组(至少包含一个正数)中寻找相邻子阵的任务。例如，对于值−2、1、−3、4、−1、2、1、−5、4的序列；最大和的连续子数组为4，−1、2、1，和6。
回答 3
Stack Overflow用户
回答已采纳
发布于 2012-01-28 01:20:53
如果允许一个空子数组，或者输入数组不能全部为负值，那么这又如何呢？
numbers.scanLeft(0)((acc, n) => math.max(0, acc + n)).max或者，如果上面的条件失败(假设输入是非空的)：
numbers.tail.scanLeft(numbers.head)((acc, n) => (acc + n).max(n)).maxStack Overflow用户
发布于 2012-01-29 00:58:14
我更喜欢折叠解决方案，而不是扫描解决方案--尽管后者肯定有优雅之处。不管怎样，
numbers.foldLeft(0 -> 0) {
case ((maxUpToHere, maxSoFar), n) =>
val maxEndingHere = 0 max maxUpToHere + n
maxEndingHere -> (maxEndingHere max maxSoFar)
}._2Stack Overflow用户
发布于 2019-06-15 18:36:38
以下代码返回开始和结束索引以及和：
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)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9041835
复制相关文章
相似问题
腾讯云开发者
