每个k = 1..n的所有大小为k的子阵列的最大总和

Question

给定大小为n的数组,对于从1到n的每个k,找到大小为k的连续子阵列的最大和.

这个问题有一个明显的解决方案,时间复杂度为O(N ²)和O(1)空间.Lua代码:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
n = #array

function maxArray(k)
    ksum = 0
    for i = 1, k do
        ksum = ksum + array[i]
    end
    max_ksum = ksum
    for i = k + 1, n do
        add_index = i
        sub_index = i - k
        ksum = ksum + array[add_index] - array[sub_index]
        max_ksum = math.max(ksum, max_ksum)
    end
    return max_ksum
end

for k = 1, n do
    print(k, maxArray(k))
end

有没有更低时间复杂度的算法？例如,O(N log N)+附加内存.

相关话题:

• 卡丹的算法

Answer 1

以下过程可能对您有帮助

\n\n

1) 选取前 k 个元素并创建大小为 k 的自平衡二叉搜索树 (BST)。

\n\n

2) 运行 i = 0 到 n \xe2\x80\x93 k 的循环

\n\n

\xe2\x80\xa6..a) 从 BST 中获取最大元素，并打印它。

\n\n

\xe2\x80\xa6..b) 在 BST 中搜索 arr[i] 并将其从 BST 中删除。

\n\n

\xe2\x80\xa6..c) 将 arr[i+k] 插入 BST 中。

\n\n

时间复杂度：\n第 1 步的时间复杂度为 O(kLogk)。步骤 2(a)、2(b) 和 2(c) 的时间复杂度为 O(Logk)。由于步骤 2(a)、2(b) 和 2(c) 处于运行 n-k+1 次的循环中，因此完整算法的时间复杂度为 O(kLogk + (n-k+1)*Logk)也可以写成 O(nLogk)。

\n