问题标签 [kadanes-algorithm]

以下是来自名为 codility 的编码面试网站的演示问题：

字符串 S 的前缀是 S 的任何前导连续部分。例如，“c”和“cod”是字符串“codility”的前缀。为简单起见，我们要求前缀不为空。

字符串 S 的前缀 P 的乘积是 P 出现的次数乘以 P 的长度。更准确地说，如果前缀 P 由 K 个字符组成，并且 P 在 S 中恰好出现 T 次，则乘积等于 K * T。

例如，S = "abababa" 具有以下前缀：

• "a"，其乘积等于 1 * 4 = 4，
• "ab"，其乘积等于 2 * 3 = 6，
• "aba"，其乘积等于 3 * 3 = 9，
• “abab”，其乘积等于 4 * 2 = 8，
• "ababa"，其乘积等于 5 * 2 = 10，
• “ababab”，其乘积等于 6 * 1 = 6，
• “abababa”，其乘积等于 7 * 1 = 7。

最长前缀与原始字符串相同。目标是选择使产品价值最大化的前缀。在上面的示例中，最大乘积为 10。

以下是我在 Java 中需要 O(N^2) 时间的糟糕解决方案。显然可以在 O(N) 中做到这一点。我在想 Kadanes 算法。但我想不出任何方法可以在每一步编码一些信息，让我找到运行的最大值。任何人都可以为此想到一个 O(N) 算法吗？

有人可以带我了解 Kadane 算法中发生的事情吗？想检查我的理解。这就是我的看法。

您正在遍历数组，并且每次将 ans 变量设置为看到的最大值，直到该值变为负数，然后 ans 变为零。

同时，每次循环都会覆盖 sum 变量，直到之前看到的和之间的最大值或迄今为止最大的“ans”。循环完成执行后，您将获得迄今为止看到的最大总和或答案！

所以我试图通过HackerRank上的动态编程轨道。

问题提示如下。

给定一个包含 N 个元素的数组 A={a1,a2,…,aN}，找出 a 的最大可能和

连续子阵列 非连续（不一定连续）子阵列。不应考虑空子数组/子序列。

输入格式

输入的第一行有一个整数T。T案例如下。每个测试用例都以整数N开头。在下一行中，后面是N个整数，表示数组A的元素。

禁忌：

您考虑的子数组和子序列应该至少有一个元素。

输出格式

二，空格分隔的整数，表示最大连续和非连续子数组。应至少选择一个整数并将其放入子数组中（在所有元素均为负数的情况下可能需要这样做）。

样本输入

样本输出

解释
在第一种情况下：连续和非连续元素的最大总和是所有元素的总和（因为它们都是正数）。

在第二种情况下： [2 -1 2 3 4] --> 这形成了具有最大和的连续子数组。对于一组不必要连续的元素的最大总和，只需添加所有正元素。

所以上面的代码通过了除了一个测试用例之外的所有测试用例。这是非常大的，所以我决定将所有测试用例上传到一个单元测试中并在我的本地环境中运行以查看发生了什么。

这

关于 dp 函数吐出的非连续答案，有两个数字不正确。这可能是从整数转换为字符串的问题吗？

我意识到我正在将 unicode 与 python 字符串进行比较，但这似乎并不重要，因为我已经尝试过相反的方法，所以我认为这不是问题，但我可能是错的。

我已经在 Python 2 中为具有已知边界的 2D 数组实现了 Kadane 算法，但我正在使用该实现进行在线竞赛，并且所花费的时间超过了给定的时间。

所以这让我想到是否可能有另一种类似于 Kadane 的算法具有更小的复杂性，或者我的代码是否可以以某种方式进行优化。我的实现适用于任何尺寸为Nx的数组M和一个尺寸为maxRowsx的子数组maxCols。

maxSumSubarray.py

测试.txt

运行

它给

这是正确的，是以下矩形：

我也尝试过其他尺寸，我很确定它工作正常。唯一的问题是时间/复杂性。任何帮助，将不胜感激！谢谢你的时间。

我想更新最好的开始索引如果我有一个数组 A={-1,-2,5,0,1} 最好的开始应该是索引 2 和最好的结束索引 4 我得到了最好的结束，但我不知道如何更新这里的最佳起始 Max 子数组 = 6 (5+0+1)

我正在尝试在 Prolog中实现Kadane 的算法。要求之一是尾调用（递归）。

我尝试了很多可能性，但没有成功。这是我的代码：

NewH，NewS 是临时值（我们不能在 Prolog 中分配一个值两次，对吧？）。我可以要求一个提示吗？

编辑：

在 Call(11) 中，我从这个简单的例子中得到了一个很好的结果 (6)。如何在此时结束函数而不返回？这是我的问题。

此代码的结果是 S = 0，而不是 S = 6。

最终编辑（工作代码）：

在哪里：

• S - 最终结果，
• F - maximum_so_far，
• H - maximum_ending_here,
• X - 列表头，
• L - 列表，
• NewH，NewF - 温度值。

谢谢您的帮助 ：）

我试图找到最大连续数组总和（包括负数。）请帮助我找出我错的一个案例。

例如，我们有

这甚至很棘手，因为我们有负数和一个额外的变量 k。k可以是任何值，负数，不要做任何假设。

我无法参考https://en.wikipedia.org/wiki/Maximum_subarray_problem和https://www.youtube.com/watch?v=yCQN096CwWM来解决这个问题。

有谁能够帮我？最好使用 Java 或 JavaScript。

这是最大值（无变量 k）的经典算法 o(n)：

我想收集所有子数组以在 javascript 中有效地进行进一步计算。我不确定这是否可行，但是对于子数组 sum kadane 的公式似乎是 o(n)，这比其他方法更有效。但我不确定如何在每一步存储数组。

与这个quora question类似，对我来说，伪代码还不够。感谢您的进一步细分。

另一个元链接

[3, 3, 9, 9, 5] 的一个例子

我了解 Kadane 算法（数组中所有顺序子数组的最大总和）如何在“伪代码”中工作的逻辑，并且我确信我可以将它实现为 C 或 C++ 中的函数。但是，我正在尝试使用 Scheme（Racket；文件扩展名是 .rkt）中的列表来实现它，我对此没有经验。

我正在寻找的最终结果是......

到目前为止，我已经开发了两个可以在 maxsum 函数中使用的辅助函数。

(1) size：返回列表中元素的个数。

(2) sum：返回列表中所有元素的总和。

我将如何定义/设计 maxsum 函数？