问题标签 [kadanes-algorithm]

Kadane 的算法可以找到我们最大的连续子数组和以及开始和结束索引，但连续子数组不一定总是最小的。例如：10 5 -12 7 -10 20 30 -10 50 60。整个数组的累积和是 150。最后 5 个元素的累积和也是 150。你将如何修改算法以找到最小的子数组？

目标：评估在下面的连续子数组中找到最大和的算法。

注意：用 C++ 编写

当我研究 Kadane 使用动态编程成功解决的问题时，我想我会找到自己的解决方法。我通过使用一系列递归调用来做到这一点，具体取决于通过缩短数组的末端是否可以使总和更大。见下文。

我知道 Kadane 的算法需要 O(n) 时间。我在计算算法的大 O 时遇到问题。它也会是O（n）吗？因为它使用 O(n) 计算总和，之后的所有调用都使用相同的时间。我的算法比 Kadane 的算法有什么优势吗？Kadane 的算法在哪些方面更好？

假设您有一个有序的、索引的正值列表。这些正值被 0 值中断。我想确定是否存在不被 0 值中断且总和超过某个阈值的连续子数组。

简单的例子：

在上面的例子中，没有被 0 中断的最大连续子数组是从 index2到 index5包括在内，这个子数组的和是15。

因此，对于以下阈值和20，结果应分别为和。104FALSETRUETRUE

注意我不一定要找到最大的子数组，我只需要知道是否有任何不间断的子数组总和超过定义的阈值。

我怀疑这个问题是 Kadane 算法的变体，但我不太清楚如何调整它。

增加的复杂性是我必须在 Excel 或 Google 表格中执行此分析，而且我不能使用脚本来执行此操作 - 只能使用内置公式。

我不确定这是否可以做到，但我将不胜感激任何意见。

我试图从二维矩阵中找出大小为 k 的最大和子矩阵。

我已经正确实现了一切，但我仍然得到：

索引超出范围 -1 异常

我对这件事的想法如下：

1. 将原始矩阵预处理为，pre_processes[][]以便我可以在恒定时间内找到 sm 。

2. 如果其中任何一个 row-k 或 col-k 大于 0，则从行和列的索引 k-1 开始，如果两者都更大，则从当前总和中减去该值，加上它们的联合，这将是pre_processes[row-1][column-1]

代码：

当我运行此代码时，它向我显示地址清理程序的运行时错误：地址处的堆缓冲区溢出：我在那里做了什么？

我正在实现一个程序，该程序使用 kadane 算法计算二维数组的最大小计。但是，我得到了逻辑错误。我想我在 for 循环中犯了错误，但我找不到它。

这是我的代码有问题的部分。

我从 leet 代码中得到了这个问题，我从 YouTube 教程中得到了这个答案，但我不明白 max 的部分。因为 max 是arr[0]并且 value 是-2，即使它进入循环内部，它也只是-2max 返回 value 6。

怎么可能？

我想编写一个函数来确定数组中任何连续子数组可以形成的最大和。

我的尝试

我的想法如下：

基本思想应该是正确的，但我无法在代码中正确实现它。感谢所有阅读本文甚至帮助初学者的人！

我遇到了一个在线测试问题，他们给出了一串字符和每个字符的值。每个字符的值在 [-10, 10] 范围内。问题是要找到一个以相同字符开头和结尾并且具有最大值的子字符串。在用值替换字符后，该问题很容易简化为最大子数组和问题的扩展版本。约束是起始值和结束值将相同。我想出了一个天真的解决方案，但还不够好。谁能告诉我如何使用 Kadane 的算法或任何其他具有更好时间复杂度的算法来解决这个问题？

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping subproblems [1]. For this question, we going to focus on the latter property only.

There are various definitions for overlapping subproblems, two of which are:

• A problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times OR a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems [2].
• A second ingredient that an optimization problem must have for dynamic programming to apply is that the space of subproblems must be "small" in the sense that a recursive algorithm for the problem solves the same subproblems over and over, rather than always generating new subproblems (Introduction to Algorithms by CLRS)

Both definitions (and lots of others on the internet) seem to boil down to a problem having overlapping subproblems if finding its solution involves solving the same subproblems multiple times. In other words, there are many small sub-problems which are computed many times during finding the solution to the original problem. A classic example is the Fibonacci algorithm that lots of examples use to make people understand this property.

Until a couple of days ago, life was great until I discovered Kadane's algorithm which made me question the overlapping subproblems definition. This was mostly due to the fact that people have different views on whether or NOT it is a DP algorithm:

• Dynamic programming aspect in Kadane's algorithm
• Is Kadane's algorithm consider DP or not? And how to implement it recursively?
• Is Kadane's Algorithm Greedy or Optimised DP?
• Dynamic Programming vs Memoization (see my comment)

The most compelling reason why someone wouldn't consider Kadane's algorithm a DP algorithm is that each subproblem would only appear and be computed once in a recursive implementation [3], hence it doesn't entail the overlapping subproblems property. However, lots of articles on the internet consider Kadane's algorithm to be a DP algorithm, which made me question my understanding of what overlapping subproblems means in the first place.

People seem to interpret the overlapping subproblems property differently. It's easy to see it with simple problems such as the Fibonacci algorithm but things become very unclear once you introduce Kadane's algorithm for instance. I would really appreciate it if someone could offer some further explanation.