Scala中的Kadane算法 [英] Kadane's Algorithm in Scala

问题描述

有人用功能样式完成了 Kadane算法的Scala实现吗?

编辑说明:链接上的定义已更改，导致对该问题的答案无效-这表明了为什么问题(和答案)应该是独立的而不是依赖外部链接.这是原始定义:

在计算机科学中，最大子数组问题是在一维数字数组(包含至少一个正数)中找到具有最大和的连续子数组的任务.例如，对于值-2、1，-3、4，-1、2、1，-5、4的序列；总和最大的连续子数组是4，-1，2，1，总和为6.

解决方案

如果允许一个空的子数组或输入数组不能全部为负，那么该怎么办?

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

或者，在上述条件之上(假设输入为非空)失败:

  numbers.tail.scanLeft(numbers.head)((acc，n)= >>(acc + n).max(n)).max 

Does anyone have a Scala implementation of Kadane's algorithm done in a functional style?

Edit Note: The definition on the link has changed in a way that invalidated answers to this question -- which goes to show why questions (and answers) should be self-contained instead of relying on external links. Here's the original definition:

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

解决方案

What about this, if an empty subarray is allowed or the input array cannot be all negative:

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

Or, failing the conditions above this (which assumes the input is non-empty):

numbers.tail.scanLeft(numbers.head)((acc, n) => (acc + n).max(n)).max

这篇关于Scala中的Kadane算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！