问题标签 [kadanes-algorithm]

这是我为使用 Kadane 算法找到最大和子数组而编写的代码。

代码：

我不断得到错误的输出：

对于输入：

你的输出是：

我试图找到长度至少为 k 的非连续子数组的最大总和。

例如，k = 2 的 [1, 2, 3, 1, 7, 9] 数组应返回 21，其中子数组 [2,3] 和 [7,9] 是最大的 2 个子数组并且是不连续的 (彼此分开）在阵列内。

另一个例子是 [1, 2, 3, 4] k = 3 返回：9, [2, 3, 4]

我在这里应用的方法是给定一个随机排序的整数数组，计算 m 个大小为 k 的子数组，但是通过计算一个 presum 数组来做到这一点，这使得很难识别构成解决方案的各个数组值。正如本例中所做的那样。

可以更改此方法以显示构成总和的子数组吗？

以下是上述方法中描述的功能：

我试图找到最小总和连续子数组的开始和结束索引。我尝试了很多次，但我无法找到。我为此使用 C++。

查找最小和连续子数组的代码：

输出：minimum sum = -6

我正在使用以下程序来查找总和的最大总和和索引。我能够获得正确的索引，但无法找到正确的索引。

我正进入（状态

这是预期的，但我也想获得在这种情况下应该是 1 的起始索引

所以我期待

有什么方法可以在这里获取起始索引吗？我应该如何把变量记录开始索引？

给定一个长度为 n 的数组，带有整数（可以是负数或正数）。找到总和最小的子数组的开始和结束索引。

给定一个整数数组 nums，

找到连续的子数组（至少包含一个数字）

其中有最大的总和并返回它的总和。

例子：

输入：[-2,1,-3,4,-1,2,1,-5,4]，

输出：6

解释：[4,-1,2,1] 的最大和 = 6。

输入：[-1]

输出：-1

输入：[-2,-1]

输出：[-1]

我在我的 JS 中尝试的内容：

这是来自极客的问题陈述（链接：https ://practice.geeksforgeeks.org/problems/kadanes-algorithm/0 ）

根据编译和测试选项，我的代码运行良好。但是当我尝试提交时，它会引发多个测试用例失败的错误。

谁能帮我解决这个问题？

代码：

我的代码链接：https ://ide.geeksforgeeks.org/tXNHh28A0D

我的输入：5（测试用例数）

3（数组大小）

1 2 3（数组元素）

5

1 2 3 -2 5

10

2 9 3 -10 -20 34 28 -50 30 -1

7

4 5 -10 -50 3 9 8

8

8 9 8 -25 25 1 2

我的输出：输入测试用例的数量

输入数组的大小：输入以空格分隔的数组元素 Kadane Sum = 6

输入数组大小：输入以空格分隔的数组元素 Kadane Sum = 9

输入数组的大小：输入以空格分隔的数组元素 Kadane Sum = 62

输入数组大小：输入以空格分隔的数组元素 Kadane Sum = 20

输入数组的大小：输入以空格分隔的数组元素 Kadane Sum = 28

提交代码时收到以下错误消息：

错误的答案。!!!Wrong Answer 可能你的代码在多个测试用例（TCs）中不能正常工作。您的代码失败的第一个测试用例：

输入：（根据网站） 3 1 2 3

其正确输出为：6

我在输入测试用例（测试用例 1）中使用了相同的输入，并且输出与预期相同。

任何人都可以帮助我使用 StringBuffer 优化代码吗？

I need to Write a program that takes in a square matrix of integers and outputs the largest sub-square-matrix sum. The first line of input is an integer which indicates the dimension of the square matrix, followed by the actual matrix row-by-row.

I have a program working however, it outputs the largest sum of a rectangle and not a square which is required.

Example input:

3

1 2 3

4 5 6

-7 -8 -9

Output: Should be 16(2+3+5+6) however it is outputting 21(1+2+3+4+5+6)

Here is my code:

我有兴趣学习如何使用 foldLeft 函数在 scala 中实现 Kadane（最大子数组和）算法。我在堆栈溢出时运行了这个示例，但是我不确定我是否理解该算法的确切作用。这是算法的样子：

lambda 函数中包含的内容是否{}需要应用于每个元素？还有这条线到底是做什么的maxEndingHere -> (maxEndingHere max maxSoFar)？为什么括号中的括号用空格分隔？我很感激任何帮助，如果我的问题太无知，我很抱歉，但我是 Scala 新手

我已经编写了 Kadane 的算法，但不知何故它返回了不正确的结果。不知道为什么。这是实现。基本上就是在一个数组中找到总和最大的`ubarray

我想它应该以某种方式返回最大总和，即 7。在计算中，我看到 7 正在计算，但它返回 1。我在代码中遗漏了什么基本的东西吗？

我已经阅读了其他实现，它们也很有意义，只是没有弄清楚为什么它没有返回正确的答案。

提前致谢！