快速的最大归一化子数组总和算法？

Question

最大子数组和问题有一个非常简单的线性时间解决方案https://en.m.wikipedia.org/wiki/Maximum_subarray_problem。

相反，如果我们想最大化sum（subarray）/ sqrt（subarray length），是否存在次二次时间解？

输入数组的元素将是-infinity到+ infinity范围内的浮点值。

Answer 1

更新

我在以下测试中添加了estabroo的基于Kadane的代码版本。在我的测试中似乎显示出高达10％的差异（运行摘要进行随机测试）。

（结束更新）

尽我所能想出这么远的近似值是在搜索过程中与窗口大小的随机样本的目标二进制搜索O(log m * n * num_samples_constant)，其中m在范围。在测试中，我看到了蛮力（限于5000个元素数组，范围为±1000000000）之间的变化，而蛮力在0到30％之间变化，样本大小为200个窗口长度。（也许另一个例程可以进一步完善？）

下面的JavaScript代码运行10个测试，并报告最小和最大差异，然后在更长的数组上执行二进制搜索。

其他想法包括使用FFT生成和，但我不知道是否有一种有效的方法可以将每个和与生成它的子数组长度相关联。以及尝试找到问题的另一种表示形式：

f = sqrt(i - j) * (si - sj), for j < i
f^2 = sqrt(i - j) * (si - sj) * sqrt(i - j) * (si - sj)
    = (i - j) * (si^2 - 2si*sj + sj^2)
    = i*si^2 - 2i*si*sj + i*sj^2
      -j*si^2 + 2j*si*sj - j*sj^2

    = i*si^2 + 
      (-2sj, sj^2, -j, 2j*sj, -j*sj^2) // known before i
        dot (i*si, 1, si^2, si, 1)

（因此，如果我们在对数时间中解决了5维凸包更新，5维极点问题，并弄清楚我们的候选对象是正面还是负面，我们将很高兴:)

f = sqrt(i - j) * (si - sj), for j < i
f^2 = sqrt(i - j) * (si - sj) * sqrt(i - j) * (si - sj)
    = (i - j) * (si^2 - 2si*sj + sj^2)
    = i*si^2 - 2i*si*sj + i*sj^2
      -j*si^2 + 2j*si*sj - j*sj^2

    = i*si^2 + 
      (-2sj, sj^2, -j, 2j*sj, -j*sj^2) // known before i
        dot (i*si, 1, si^2, si, 1)