问题标签 [kadanes-algorithm]

我在 java 中有以下 Kadane 算法的实现。基本上是找到连续子数组的最大和。

但是，如果数组中存在负数和正数的组合，则这不起作用，例如：

最多应返回 12。截至目前，它返回 5

上面的代码返回最大子数组的总和。

我将如何返回具有最大总和的子数组？

有没有人以函数式风格完成Kadane 算法的 Scala 实现？

编辑说明：链接上的定义发生了变化，导致该问题的答案无效——这说明了为什么问题（和答案）应该是独立的，而不是依赖于外部链接。这是原始定义：

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

我有以下Kadane 算法的实现来解决数组的最大子数组的问题：

当我使用以负数开头的序列（例如-1, 2, 3给出结果4, [0,2]而不是5, [1,2].

对于我的一生，我找不到错误在哪里。也许是算法设计的缺陷？

提前致谢。

如果我有那个数组，我的 Kadane 算法实现来找到最大子数组就可以了：

但是，如果我有一个包含所有负数的数组：

它不起作用，它应该返回 -10，但我得到 0。

我怎样才能让它也适用于负数？

谢谢！

我试图解决以下问题：

加权和问题

我之前做过的最接近的问题是 Kadane 的算法，所以我尝试了“此处最大结尾”的方法，这导致了以下基于 DP 的程序。这个想法是将问题分解为更小的相同问题（通常的 DP）。

但是这个程序在指定的时间限制内不起作用（空间限制很好）。请给我一个关于在这个问题上使用的算法的提示。

编辑。

这是代码的解释：就像在 Kadane 中一样，我的想法是查看特定的 C[i]，然后对以 C[i] 结尾的 m 子序列取最大加权和，最后取所有的最大值对所有 i 的这些值。这将为我们提供答案。现在请注意，当您查看以 C[i] 结尾的 m 子序列并取最大加权和时，这相当于取 C[0] 中包含的 (m-1)-子序列的最大加权和到 C[i-1]。这是一个较小的问题，与我们原来的问题相同。所以我们使用递归。为了避免重复调用函数，我们制作了一个值表 f[i][j]，其中 f[ii][j] 是问题的答案，与我们的问题相同，将 n 替换为 i，将 m 替换为j. 也就是我们建立一个f[i][j]的表，我们最终的答案是f[n-1][m]（也就是我们使用memoization）。现在注意到计算条目 f[i][j] 只需要前一列，只保留数组就足够了。这些数组是“a”和“b”。

抱歉，篇幅太长，忍不住了。:(

我在 javascript 中实现了 Kadane 的 Max Sub 数组问题，但似乎我最终总是在控制台中得到 0，即使存在更高的数字（我知道它做了它正在做的事情，因为 for loop from 0 - sizewhere size = subarray size）。

• 那么如何正确实现算法呢？

• 它是否也适用于所有正整数数组？

杰宾

http://jsbin.com/ajivan/edit#javascript,live

对于线性数组，寻找连续编号的最大和的问题。简单。使用Kadane 的算法可以轻松完成。. 但是现在数组是圆形的，我们需要找到连续数的最大和。因此 startindex 和 endindex 可以在数组中的任何位置。我没有得到如何及时解决它O(n)。

例如：{ 8, 9, -14, 4, 3}。

最大子sum= 4+3+8+9= 24. startindex=3 and endindex=1数组（零索引数组）。请给我一些关于如何解决这个问题的提示或算法。无需代码。

编辑：正如大家提到的，圆形数组类似于跨越两次的相同数组。但是如何在该数组上应用 Kadane 的算法并限制连续编号。到 <=n

我想用展示（n log n）的算法来实现最大子数组问题：

查找最大连续子数组，或数组中连续元素的最大总和。

假设：并非所有元素都是负数

我有一些可行的解决方案；问题在于重叠的中心数组，以及指定重叠子问题的适当索引，一些数组我得到了正确的答案，而另一些则没有。

只是为了比较和检查正确性，我实现了一个称为 Kadane 算法的解决方案（我相信复杂度是 Omega(n)）。

这是 Kandane 的算法（http://en.wikipedia.org/wiki/Maximum_subarray_problem）：

我的递归实现，使用分治法来比较子数组的最大值，然后对具有最大值的子数组进行递归调用，直到递归结束

结果：使用数组 subArrayProblem1 = {1, 2, 3, 4, 5, 6, 7, 8};

Kadane（int array []）：36 低：0 中：4 1,2,3,4,5,6,7,8,中：4 高：7 低中心：6 高中心：6

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:7 high: 7 global Max Sum:36 BUILD SUCCESSFUL (总时间: 0 seconds)

问题尽管与 Kadane 相比，全局最大总和是正确的，但低指数和高指数范围反映了最后一次递归调用。

结果：使用数组 subArrayProblem = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97}；

Kadane（int数组[]）：1607低：0中：8 100,113,110,85,105,102,86,63,中+1：9高：16 101,94,106,101,79,94,90,97,lowCenter：16 highCenter：15

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:16 high: 16 global Max Sum:1526

全局最大值不正确，注意区别其实是1个元素，也就是元素81

子数组包含正数和负数。您必须找到一个最大和子数组，使得子数组的长度大于或等于 k。

这是我使用 Kadane 算法的 c++ 代码。

我的代码运行良好，但速度很慢，我想不出任何方法来改进我的代码。我也读过这个问题查找总和可被 K 整除的最长子数组，但这不是我想要的，长度也可以大于 k。