问题标签 [kadanes-algorithm]

我正在解决一个要求最大和连续子数组的问题。我知道这个问题可以通过使用 Kadane 的算法来解决，但我不知道算法，所以我尝试自己编写问题。

这是我写的代码：

但是这段代码没有给出正确的输出，我似乎无法弄清楚出了什么问题？谁能帮我吗？

我试图在图像的任何矩形中找到最多的空白（最大白色像素），我将用另一个较小的图像覆盖。矩形的尺寸是 X 像素乘 Y 像素，由覆盖图像的大小（高度、宽度）决定。

目前我唯一的解决方案是尝试将每个像素作为叠加图像的 TLC 并计算下面有多少白色像素。一旦我达到最大值，我就可以定位叠加图像。

例如，给定一个 2x2 的固定子矩阵大小和这个数组： -

我希望最大结果为 4，坐标为 2,2

不用说，这个问题效率极低:-(

我尝试了 Kadane 的算法，但这似乎只适用于不同的值，甚至会产生一个可变大小的子矩阵。

有任何想法吗？更好的算法？

我将计算 (0,0) TLC 矩形中的空白，然后只需减去视口外的 col 或 row 并在覆盖矩形移动到基础图像上时添加新的行或 col。

给定一个由 N 个元素组成的数组 A。我们的任务是在恰好应用一次以下操作后找到最大子数组和：

. 选择任何子数组并将其中的所有元素设置为零。

例如：- 数组是 -1 4 -1 2 那么答案是 6，因为我们可以在索引 2 处选择 -1 作为子数组并将其设为 0。因此，在应用操作后，resultatnt 数组将是：-1 4 0 2。最大和子数组为 4+0+2 = 6。

我的方法是找到最小和子数组的开始和结束索引，并将所有元素设为该子数组的 0，然后找到最大和子数组。但这种方法是错误的。

你有没有觉得你的脑袋不适合算法？

我尝试解决最大子数组问题，我在 Codewars 上遇到了这个解决方案：

我了解如何使用以下方法以线性时间复杂度解决此问题Kadane's algorithm：

但我不明白为什么第一个解决方案有效。我根本无法理解它背后的想法。我觉得需要一点帮助来克服困难。

编辑：这是一个带有一些示例的Codepen

//此代码用于使用 kadane 算法的最大子数组问题。我的编译器返回错误的输出

我很难理解我发现的 Kadane 算法的这两个示例中发生了什么。我是 Python 新手，我希望理解这个复杂的算法能帮助我更好地查看/阅读程序。

为什么一个例子比另一个更好，它只是List vs Range？是否还有其他东西可以使示例之一更有效？此外，还有一些关于计算中发生了什么的问题。（示例中的问题）

我使用PythonTutor来帮助我一步一步了解到底发生了什么。

示例 1：

在 PythonTuter 中，当您在提供的屏幕截图中选择下一步时，so_far 的值变为 1。这是怎么回事？给出总和，我认为它加上 -2 + 1 即 -1，所以当 so_far 变为 1 时，这是怎么回事？

示例 2：

这一个类似的问题，当我选择 NEXT 步骤时，max_sum 从 -2 变为 4 ......但是如果它在 2 中添加元素（即 4）怎么办。对我来说，那将是 -2 + 4 = 2 ？

所以，这将是一个两部分的问题，而不是：

下面是代码片段：看到子数组的最大和是 6，但它被计算为 7。
所以 Kadane 的算法在这里失败了？！

这是一个典型的问题，需要您一次性解决。给定一个仅包含 0、1 和 2 的数组。您需要在 O(1) 辅助空间中一次性对数组进行排序。我想知道对于包含更多不同值的数组是否存在这样的单程解决方案，以及单程解决方案存在的不同值的数量的限制是什么。