arrays - Maximum_Subarray_Problem 的变体

Question

这是 Maximum_subarray_problem 的变体.

在长度为 N ( 0 <= K <= N ) 的数组中找到长度最多为 K 的连续子数组

例如。给定 [-13,-1,1,1,2,3,1,1] 和 K = 2，最大 K 子数组和为 5

寻找O(N) 解决方案。简单的解决方案是 O(N*N)，检查每对之间的范围。我觉得可以改进到O(N)。

Answer 1

让你的数组索引为 1 到 n。设 f(i) 为以 i 结尾的最大子数组，prefixSum(i) 为(包括)索引的前缀总和我。那么我们有

f(i) = prefixSum(i) - MIN(j = i - K to i - 1, prefixSum(j))

f(i) 可以通过使用 sliding window minimum 在线性时间内计算数据结构。 Here's another implementation对于队列，它支持enqueue、dequeue 和find-max/min。使用该队列作为原语，该算法在伪代码中看起来像这样:

global_max = -infinity
prefixSum[0] = 0
q = new MinQueue()
for i := 1 to n:
    prefixSum[i] = prefixSum[i - 1] + a[i]
    if i > 1
        q.enqueue(prefixSum[i - 1])
    if i - K - 1 >= 1
        q.dequeue()
    global_max = max(global_max, prefixSum[i] - q.min())