当两个元素交换时更新数组的最大和子间隔
对于给定的实数数组，Kadane的动态规划算法可以在线性时间内找到数组中的最大和子区间。然而，假设我们做了一些预处理以获得最优解以及任何所需的辅助信息，然后给我们一个换位，交换数组中的两个元素。是否有一种方案，允许在次线性时间内更新最优解子区间，并允许后续换位的未来更新？对于大小为n的数组，我希望预处理时间和额外内存为O(n^2)。
共有1个答案
这是一种对列表进行预处理的方法，在一般情况下，可以大大缩短列表的长度。如果原始列表中的一个条目发生变化，更新预处理信息也不难。
预处理过程的思想是，某些元素集合可以组合在一起，并在逻辑上作为单个元素处理。例如，如果列表中有两个正数紧挨着，如
... -1 3 4 -2 ...
那么你永远不会想在你的最大子集和中包括3，除非你也包括4。因此，在逻辑上，您可以将列表的这一部分视为
... -1 7 -2 ...
... 8 -2 4 ...
可视为
... 10 ...
这是因为如果我们包含4，那么我们也可以包含-2+8=6，从另一个方面来看也是如此。
另一个简化是负数的模拟。如果有两个负数，中间有一个正数，而正数的大小比任何一个负数都小，那么我们可以把三重看作一个数字。例如：
... -10 4 -12 ...
... -18 ...
优点是，在应用这些修改后，最大子集和正好是（减少的）列表中剩余的最大正条目！这里有一个证据：
假设我们的列表按照上面的简化进行了缩减（这意味着应用这三个中的任何一个都不会对它产生任何影响）。为了矛盾起见，假设这个简化列表的最大子集和由不止一个条目组成。所以，让我们将具有最大子集和的区间表示为：
... a1 -b1 a2 -b2 ... a(n-1) b(n-1) an ...
其中ai为正值，bi为负值。（请注意，由于显而易见的原因，两个端都不会是负数。）
一遍又一遍地应用这些参数，我们得到了一串不等式：
a1 > b1 > a2 > b2 > ... > a(n-1) > b(n-1) > an
但是最后一个不等式是一个矛盾，因为如果b(n-1)>an，那么我们可以从区间中砍掉这两个元素，得到一个更大的子集和。
（注意，我忽略了两个相邻的ai和bj相等的可能性。为了处理这种情况，您必须对符号稍微小心一点，但它很好地解决了问题，用严格的不等式更容易理解这个论点。）
最快的方法可能是保存一个包含少数几个最大子集和候选项的排序列表，并在新元素出现后有选择地更新该列表。
-
O(n^2)算法简单。有没有人对此有更好的算法？
-
在一本书（算法导论，但我不记得是哪一章）中，我学到了求解两元素间最大差值问题： 两个元素之间的最大差，使得较大的元素出现在较小的数之后。 查找数组（至少包含一个数字）中和最大的相邻子数组。 例如，给定数组[-2,1,-3,4,-1,2,1,-5,4]，相邻子数组[4,-1,2,1]的最大和=6。 为了解决的两元素间最大差异问题，可以将其转化为数组的最大子数组问题： 我在想为什么。
-
有没有一种方法可以在小于O(n^2)的时间内做到这一点。 O（nlogn）还是O(n)？
-
问题内容： 有没有更简单的方法来交换数组中的两个元素？ 问题答案： 您只需要一个临时变量。 *10年后，我们大量采用了ES6，从而 *编辑 劫持性最高答案： 给定数组，您现在可以在一行中交换值，如下所示： 这将产生数组。。
-
本文向大家介绍交换数组的第k个元素-JavaScript，包括了交换数组的第k个元素-JavaScript的使用技巧和注意事项，需要的朋友参考一下 我们需要编写一个JavaScript函数，该函数接受一个Numbers和一个数字数组，例如k（k必须小于或等于数组的长度）。 并且我们的函数应该从数组末尾的第k个元素开始替换第k个元素。 示例 以下是代码- 输出结果 以下是控制台中的输出-