问题标签 [kadanes-algorithm]

我必须解决一个类似于最大子数组问题的问题。我必须找到平均值大于 k 的最大子数组。我想到了以下技巧。我可以将大小为 n 的数组 A[] 转换为 B[]，其中 B[i] = A[i] - k。所以现在平均值必须> 0。但是平均值大于零并不仅仅意味着总和大于零吗？所以我可以直接应用 Kadane 的算法。我对吗？（总是在有 1 个正值的约束下）

谁能帮助我理解上述算法中的最佳子结构和重叠问题（DP的面包和黄油）？

Kadane 的算法 ( http://en.wikipedia.org/wiki/Maximum_subarray_problem ) 用于在一维数字数组中找到连续子数组的最大总和。

现在，如何使用它来找出具有相同最大和的此类序列的数量？可以对算法进行哪些修改以计算此类序列..

例如：

如果我错过了一些关于输入的假设，我深表歉意，但是这个算法对于像{2, -3, 1}这样的输入不会失败吗？

处理-3时， currentSum 得到2+ (-3) = -1并且 currentStartIndex 重新开始！我是否忽略了一些明显的东西？

http://www.algorithmist.com/index.php/Kadane%27s_Algorithm

我正在尝试编写一个解决最大子数组问题的程序。我可以理解 Kadane 算法在 1-D 数组上的直觉以及在 2-D 数组上的 O(N^4) 实现背后的直觉。但是，我在理解二维数组上的 O(N^3) 实现时遇到了一些麻烦。

1）为什么我们将元素与同一列中前一行的元素相加？

2）我对算法的第二部分没有理解

试图在网上寻找解释，但无济于事。希望能在这里得到一些帮助！

提前致谢！

应用 Kadane 算法来获得最大产品子数组似乎很棘手。虽然我能够获得最大产品，但我并没有真正获得最大产品子数组的正确范围。

http://www.geeksforgeeks.org/maximum-product-subarray/ 解释了获得最大产品的方法，但我不明白我们如何获得子数组的范围。

有人可以帮我理解范围问题吗？这是一个标准的面试问题，我想确保我理解产品案例的逻辑，而不是仅仅说可以修改最大和子数组以回答最大产品子数组案例。

谢谢！！

我试图弄清楚如何为 Kadane 的 2D 矩阵算法实现 C# 代码。我在这里找到了 1D 版本：

Kadane 算法找到最大和的子数组

但我想要一个2D版本。基本上，给定一个正数和负数的矩阵 N x N，我需要找到一个子矩阵，其中所有元素的总和最大。

我有一个稀疏的 mxn 矩阵，其中包含 N 个非零条目。
的修改版本Kadane's 2-d algorithm可以及时找到最大和子矩形O(m N log n)，这优于传统的 Kadane 算法，O(m^2 n)用于足够稀疏的矩阵。
现在我想知道如果矩阵中的一个条目发生变化，是否可以快速更新最优解。
我所说的“快速”是指类似O(m log n) time or better.
有可能矩阵不必是稀疏的a solution, however a solution when N = O(min(m,n)) would be ok。

我试图找到一个关于 subarray 的最小切片的 codility 问题的解决方案，并且我设计了一个使用 Kadane 算法的修改版本的解决方案。我目前已经获得了 90/100 并设法通过了 O(n) 中的几乎所有测试。但是，我似乎无法通过“medium_range，增加，减少（legth = ~100）和小功能，得到 5 预期 3”，我不知道为什么。这可能是解决方案的重复，但我使用的解决方法略有不同。

我的逻辑如下：

a) 如果我们有一个数组 MinA，其中 MinA[k] 表示从 k 开始且最小长度为 2 的子数组的最小平均切片

b) 然后如果我们遍历 MinA 并找到数组的最小值，那么这将是整个数组的最小平均切片（然后返回索引位置）

c) 要创建这个 MinA，我们从数组的倒数第二个元素开始，MinA[A.length -2] 是 A 的最后两个元素的平均值

d) 我们将计数器向左移动一位；MinA[counter] 必须是 A[counter] 和 A[counter + 1] 的平均值，或者是元素 counter 和 MinA[counter + 1] 中元素的平均值

e) 如果 d 不为真，那么这意味着 MinA[counter + 1] 不是从 counter + 1 到从 counter + 2 到 N 的某个元素的最小平均切片

我想知道我是否遗漏了什么？

我对这里给出的实现是否正确持怀疑态度，所以我完全用 C++ 实现了它，而对于上面的测试用例，它不起作用。我找不到算法错误的地方？