问题标签 [kadanes-algorithm]

我一直在尝试获取子数组的最大乘积范围（为求职面试而学习）。

此处已提出此问题（但未提供有效答案）。 使用 Kadanes 算法获取最大乘积子数组的范围

技巧/算法在这里解释得很好：http: //www.geeksforgeeks.org/maximum-product-subarray/

我能够轻松获得最大产品，但经过多次尝试，仍然无法弄清楚如何获得范围（左右索引正确）。有人可以帮忙吗？？

我已经粘贴了我的代码，所以你可以快速复制并运行它。

以下是示例输出：

正如你所看到的，我得到了最大的产品，但范围是错误的。

请帮忙。

给定一个数字数组，求最小和且子数组的长度不能为 0。

我知道我可以使用 kadane 的算法，但问题要求子数组的长度不应为 0。因此，我的实现无法处理数组的所有元素都是正数的情况。

例如，给定以下数组：2、5、3、8、4，最小和为 2。

它还必须适用于普通数组，例如：-5、-4、5、-1、2，最小总和为 -9（前两个元素的总和）

我如何实现这一目标？

这是我的实现：

有一个A包含（正负）整数的数组。找到一个（连续的）子数组，其元素的绝对和最小，例如：

我首先实现了一个蛮力算法，它是O(N^2)or O(N^3)，尽管它产生了正确的结果。但任务指定：

经过一番搜索，我认为也许可以修改 Kadane 的算法以适应这个问题，但我没有做到。

我的问题是 - Kadane 的算法是正确的方法吗？如果没有，您能否指出我正确的方向（或在这里命名一个可以帮助我的算法）？我不想要现成的代码，我只需要帮助找到正确的算法。

一个仅包含 0 和 1 的数组作为输入给出。您可以选择数组 i 和 j 的任意两个索引并翻转它们之间的所有元素（即 0->1 和 1->0）。求翻转后得到的数组的最大和。例如：对于 [0,1,0,0,1,0]，答案是 4。（从索引 2 翻转到 3）。

这是我的方法：
1）为数组中的所有索引找到前缀总和（保持在 sum[i] 中）。
2）翻转原始数组中的所有位。
3) 使用 Kadane 的算法找到最大子数组和 MAXSUM。令最大子数组的开始和结束索引为 i 和 j。
4) 答案是 sum(i-1)+MAXSUM+sum(n-1)-sum(j)。

请告诉我我的方法是否正确。

我是 Prolog 的新手，正在尝试解决最大子数组问题的实例。

我有以下非常优雅的 C++ 代码：

这是我的 Prolog 代码：

我尝试从中获取最大总和，列表f(L,M,N)在哪里，是结果（最大总和，也像 C++ 代码中的变量“maxsofar”），是一个中间变量，作为 C++ 代码中的“maxendinghere”。我想从它以前的列表中得到答案，变量的关系和C++代码一样。LMNLL1

但是，以下查询不起作用：

我不知道问题出在哪里。

I'm reading Cormen's "Introduction to Algorithms".

For the linear algorithm for Max Sum Subarray problem I came up with my own solution. Didn't check existing one (Kadena's) before implementing.

Now I'm testing it with different test scenarios and always have better results than Kadena's. I don't believe in such a luck, but can't find what have I missed. Could you take a look whether it is a working solution?

Update The idea of code is to keep in track only one subarray, and adding to its' tail numbers, when numbers are that low that sum becomes negative - set beginning of array after the tail. Additionally negative items in the beginning are being ignored. head of subarray is just shifted forward. Everytime sum appears to be maximum - maxSum and limits are updated.

给定一个带有 +ve 和 -ve integer 的数组，找到最大和，这样你就不能跳过 2 个连续的元素（即你必须至少选择其中一个才能向前移动）。

例如：-

10、20、30、-10、-50、40、-50、-1、-3

输出：10+20+30-10+40-1 = 89

问题是：

给定一个二维数组 [1:m,1:n]，我们必须找到一个最大和子数组 [a:b,c:d] 其中 1<=a<=b<=m 和 1<=c<=d <=n 使得数组元素的总和为 (Summation)A[i,j] 其中 a<=i<=b 和 c<=j<=d 时间复杂度 O(mn min(m,n ) 对数最大值(m,n))

我想知道如何解决这个问题。我在想以下 -

1）我将在每一行上使用Kadane的算法，从2x2矩阵的中间到左右找到每个元素的累积和

2）根据升序对右侧的总和进行排序

3）将左侧的每个元素映射到右侧的最大元素并选择具有最大值的行..

4）也从2x2矩阵的中间到顶部和底部重复该过程（累积和）

5）重复步骤2和3相同

6）结合两种方法得到的最大值作为最大和子数组

这是我的程序，用于从给定数组中找到子数组（连续）的最大和。使用 kadane 的算法非常容易。

但我也想找到具有最大总和的连续子数组的开始和结束位置。我尝试在上面的程序中添加几行来做到这一点，但它没有用。所以我的问题是如何获得具有最大总和的子数组的开始和结束位置？谢谢。

我们大多数人都熟悉最大和子数组问题。我遇到了这个问题的一个变体，它要求程序员输出所有子数组和以某个数 M 为模的最大值。

解决这个变体的天真的方法是找到所有可能的子数组和（这将是 N^2 的数量级，其中 N 是数组的大小）。当然，这还不够好。问题是——我们怎样才能做得更好？

示例：让我们考虑以下数组：

6 6 11 15 12 1

令 M = 13。在这种情况下，子数组 6 6（或 12 或 6 6 11 15 或 11 15 12）将产生最大和（= 12）。