问题标签 [kadanes-algorithm]

我目前正在做一个类似于最大连续子阵列问题的问题。但是，我可以找到最多两个不重叠的连续子阵列，而不是只找到一个连续的子阵列。

例如，对于下面的测试用例，答案是 20，因为我们可以取除 -20 之外的所有值。

为此，我实现了以下代码：

这是函数调用：

dp 数组在函数调用之前已经填充了 -1。nums 数组包含 n 个元素并且是零索引的。

Ideone.com 链接是这样的：http: //ideone.com/P5PB7h

虽然我的代码确实适用于上面显示的示例测试用例，但它对于其他一些测试用例（我不可用）却失败了。是否有任何边缘情况没有被我的代码捕获？我哪里错了？感谢您的帮助。

我尝试提出一些这样的边缘案例，但我无法这样做。

到目前为止我所做的：

我用 Kadane 的算法找到了总和。

我创建了一个向量“res”，它在满足条件时存储元素。

问题： 例如，当输入是一个数组时： {-2, -3, 4, -1, -2, 1, 5, -3} 结果数组包含右子数组元素以及添加的 1 个额外元素当条件失败时。

tldr：代码将输出子数组返回为：{4 -1 -2 1 5 -3} 而正确的输出应该是 {4, -1, -2, 1, 5}

我试图通过解决 Codality 问题来提高我的技能。我到达了这个：https ://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

我实际上从理论上理解解决方案：

1. 在数组上使用 Kadane 算法并将总和存储在每个索引处。
2. 反转数组并执行相同操作。
3. 通过一次循环遍历两个结果集，找到两者之和为最大值的点。
4. 最大值是最大双切片。

我的问题不是关于如何解决问题。我的问题是关于人们如何想象这将是解决这个问题的方式。至少有 3 个不同的概念需要使用：

1. 理解如果数组中的所有元素都是正数或负数，则与数组中有一些正元素和负元素时的情况不同。

2. Kadane 算法

3. 向前和向后遍历阵列。

尽管如此，Codality 还是将此问题标记为“无痛”。

我的问题是我错过了什么吗？在不了解其中一些概念的情况下，我似乎很难解决这个问题。

有没有一种技术可以让我从头开始和非常基本的概念，然后逐步达到解决这个问题所需的概念。还是在开始问题之前我就应该知道这些概念？

我如何准备自己来解决将来我不知道所需概念的问题？

我有一个A包含整数（正数、负数或零）的数组。所以，我想获得最大绝对范围总和（类似于Kadane's algorithm，但具有绝对值）。例如，设 A 为：

A = [-3, 2 ,-3, 1]

所以答案是 4abs(A[0] + A[1] + A[2]) = 4.

我试图使用 Kadane 的算法找到解决方案，保持当前的最大总和，但在某些情况下似乎不起作用。有没有办法得到答案？

Expected time complexity: O(n*log(n))

我知道使用 Kadane 算法找到最大 2D 子矩阵的算法是 O(m^2*n)，其中 m 是列，n 是行。但是，如果我们必须忽略整个矩阵中的 1 个元素（即我们将其值更改为 0，然后我们将获得最大子矩阵），是否有一种算法可以找到最大 2D 子矩阵？

我希望时间复杂度不要高很多，但我找不到有效的方法来做到这一点。似乎困难在于知道要忽略哪个元素，而无需逐个尝试所有元素，然后每次都计算最大子矩阵，我相信这将是 O(m^3*n^2) 。我什至不确定这是否可能，但我觉得可能有办法。

编辑：我看到这篇文章是关于一维数组的 O(n) 解决方案，但我认为将它推广到更高维数组并不是那么简单。不过，这可能是一个有效的提示。

问题：
给定两个数组A和B，大小均为n，求区间[i,j] (0 <= i,j <= n-1)，找到使 的值最大化的V = sum(A[i:j]) - min(B[i:j])。

没有数组B扭曲，这个问题只是最大子数组和问题，可以O(N)用 Kadane 算法解决。现在，我们有第二个数组，我们从范围中选择最小元素，然后从总和中减去它。

一个简单的算法是做一个双循环来计算每个(i,j)区间，但是这种幼稚的方法有O(N^2)时间复杂度。

我一直试图找到一个O(N)，或者至少是一个O(NlogN)算法，但我还没有能够实现它。

我将不胜感激任何想法，谢谢！

编辑：彼得解决方案的实现供参考：

输出：

我一直在解决算法简介 - CLRS 中的练习，并且遇到了在线性时间内解决最大连续子阵列（Q 4.1-5）。请在下面查看我的解决方案。我一直在为这个练习寻找在线评委，但没有找到。在我寻找解决方案时解决它后，我发现 kadane 的算法似乎与我的实现不同，而且当所有数字均为负数时，该解决方案也给出了正确的输出。

除了将手动测试用例输入程序之外，有没有办法检查这个算法的有效性？

我的算法如下图所示：

在此基础上，我编写的代码如下所示：

当. output 0_ array is [-1,-2,-3,-4]在我当前的代码中我应该纠正什么吗？

假设 max_sequence(Array A): 是 Kadane 算法的解决方案。

你有一个数组：5,-3,-4,8,-1,12,-6,+4,+4,-14,+2,+8

你把这个数组缩短为正负序列的条纹：

所以现在数组是：+5,-7+8,-1,+12,-6,+8,-14+10

两个数组返回的最大序列相同。

你能否从数学上证明存在/不存在从函数 max_sequence 返回不同输出的整数序列（至少包含一个正整数）？

尝试使用 Kadane 的算法，如下所述：https ://www.youtube.com/watch?v=OexQs_cYgAQ&t=721s

在这个数字数组上：[-5, 10, 2, -3, 5, 8, -20]。

答案是10 + 2 – 3 + 5 + 8 = 22

但是，当我运行以下代码时，我得到了这个：

sumArray = [ 0, 20, 24, 24, 28, 44, 44 ]

不知道如何24和更高的数字进入那里:(并且22丢失了。

下面的代码：

这个想法是我只需填写 sumArray 然后按最大数对其进行过滤。但是我没有得到22，而是一大堆更大的数字？

任何想法为什么？