arrays - 交换两个元素时更新数组的最大和子间隔

Question

对于给定的实数数组，KADAN的动态规划算法可以在线性时间内找到阵列中的最大和子区间。然而，假设我们已经做了一些预处理来获得最优解以及任何所需的辅助信息，然后给出了换位，交换了数组中的两个元素。是否有一个方案允许在次线性时间内更新最优解子区间，并允许后续换位的未来更新？我正在寻找预处理时间和额外的内存o(N^2)对于一个数组大小N。

Answer 1

这是一种预处理列表的方法，在一般情况下，可以大大缩短列表的长度如果原始列表中的某个条目发生更改，则更新预处理信息也不太困难。
预处理过程的思想是，可以将某些元素集合组合起来，并在逻辑上将其视为单个元素。例如，如果列表中有两个正数相邻，如

... -1 3 4 -2 ...

然后，你永远不想把3包含在最大子集和，除非你也包括4。所以，你可以在逻辑上把你列表中的这一部分当作

... -1 7 -2 ...

相邻的负数也是如此。所以，从现在起，我们可以假设列表条目的符号是交替的。
我们还需要另外两个简化：
如果两个正数之间有负数，负数比两个正数中的任一个都小，那么就永远不希望在最大子集和中包含正数而不包括另一个正数。例如：

... 8 -2 4 ...

可以看作

... 10 ...

这是因为如果我们包括 4，那么我们也可以包括 -2 + 8 = 6，类似地从另一方面。
另一个简化是对负数的模拟。如果有两个负数之间有一个正数，并且正数的大小比任何一个负数都小，那么我们可以把三个数当作一个数。例如：

... -10 4 -12 ...

可以看作

... -18 ...

很难理解为什么这是有效的假设我们的最大子集和包含了这三个数字中的一个，如 -12。当然它也包括 4，因为这使得子集和更大。但它当然也必须包含 -10，因为如果它不包含，那么我们就可以从区间的末尾剪掉 4 - 12 = -8，使我们的子集和更大。直观地说，如果这个三元组生活在最大子集和区间中，则在区间的中间。
您需要递归地应用这三个简化，直到没有一个在列表中产生更改为止这可能需要很长的时间，但是可以通过跟踪自上次迭代以来列表中哪些区域发生了更改，并且只使用重复的应用程序来命中这些区域来缩短时间。
其优点是，在应用这些修改之后，最大子集和正好正好是（减少）列表中最大的正项。这是一个证据：
假设我们的列表按照上面的简化进行了缩减（也就是说，应用这三个列表中的任何一个都不会对它产生任何影响）。假设为了矛盾起见，这个减少列表的最大子集和数由一个以上的条目组成。那么，让我们用最大子集和来表示区间：

... a1 -b1 a2 -b2 ... a(n-1) b(n-1) an ...

其中， ai为正， bi为负。（请注意，由于明显的原因，两端都不是负数。）
我们现在要提出我们的矛盾：
首先，注意 a1 < b1，因为否则我们可以将这两个元素从那一端切掉，得到一个更大的子集和。同样，因为我们的列表被减少了，如果 b1 > a2那么 b1 < a2将被折叠成一个条目（因为我们已经知道 a1 -b1 a2。
接下来，请注意 b1 < a1这是因为如果 a2 > b2，那么根据第三个简化，这个事实与 a2 < b2结合将导致 b1 < a2折叠为一个条目。
反复应用这些论点，我们得到一系列不等式：

a1 > b1 > a2 > b2 > ... > a(n-1) > b(n-1) > an

但最后一个不等式是矛盾的，因为如果 -b1 a2 -b2，那么我们就可以把这两个元素从区间中去掉，得到一个更大的子集和。
（注意，我忽略了相邻两个 b(n-1) > an和 ai相等的可能性。你必须对符号稍微小心一点，才能处理好这个问题，但结果很好，而且这个论点更容易用严格的不平等来解释。）
您需要保留原始列表的副本，并且当元素的值发生更改时，应用“围绕”该元素的简化步骤，以避免对列表的更多内容进行重采样。
请注意，最初必须（实际上，能够）进行的简化越多，最终的列表就越小，从而节省了以后的运行时间可能这的预期（聚合）运行时间比 bj好，但我不想考虑它，这是一个需要分析的毛茸茸的算法。
保持几个最高的最大子集和候选的排序列表可能是最快的，并且在新的元素出现之后有选择地更新该列表。