找到数组的不相交序列的最大总和

Question

我有一个整数序列(-10 ^ 6到10 ^ 6)A.我需要选择A的两个连续的不相交子序列,比如x和y,它们具有相同的大小n.

之后,您将计算由?x(i)y(n?i+1)(1索引)给出的总和

而且我必须选择x和y,以便最大化和.

Eg: 
Input: 
12
1 7 4 0 9 4 0 1 8 8 2 4 

Output: 120

Where x = {4,0,9,4}
y = {8,8,2,4}

?x(i)y(n?i+1)=4×4+0×2+9×8+4×8=120

现在,我想到的方法是O(n ^ 2),如下所示:

初始化两个变量l = 0和r = N-1.这里N是数组的大小.
现在,因为l=0,我将计算总和,(l<r)而基本上是指从数组中的第0个位置开始的子序列.然后,我将递增l和递减r,以便得出从上面的位置+ 1开始并在右侧开始的子序列right-1.

我可以使用更好的方法吗？什么更有效率？我想过排序,但我们不能对数字进行排序,因为这会改变数字的顺序.

Answer 1

警告：此方法假设数字为非负数，因此此解决方案不能回答发布者的实际问题，现在已经澄清允许负输入值。

技巧1

假设数字始终为非负数，则在给定序列相遇位置的情况下，最好使序列尽可能宽。

我们可以通过对 i 的所有值求和来将总和更改为标准卷积。这会产生两倍于期望结果的结果（因为我们既得到 x 与 y 的乘积，又得到 y 与 x 的乘积），但我们可以在最后除以 2 以获得原始答案。

您现在尝试找到信号与其自身卷积的最大值。有一个标准方法可以做到这一点，即使用快速傅立叶变换。有些库会内置此功能，例如在 Scipy 中有fftconvolve。

请注意，您不允许重复使用中心值（例如，对于序列 1,3,2，我们无法生成 x 1,3 和 y 3,1），因此我们需要检查卷积输出的替代值。

我们现在可以通过以下方式在 Python 中计算答案：

import scipy.signal
A = [1, 7, 4, 0, 9, 4, 0, 1, 8, 8, 2, 4]
print max(scipy.signal.fftconvolve(A,A)[1::2]) / 2