长度至多为 k 的连续子序列的最大和

Question

我正在尝试修改 Kadane 算法以解决更具体的问题。

def max_Sum(arr, length, k):
if length < k:
    print('length of array should be greater than k')

res = 0
for i in range(0, k):
    res += arr[i]

current_sum = res

for i in range(k, n):
    if k == n:
        for j in range(0, k-1):
            res += arr[j]
        current_sum = res
    else:
        current_sum += arr[i] - arr[i-k]
        print(res, current_sum)
        res = max(res, current_sum)

return res

这是最大子数组问题的代码。我想要做的是找到长度最多为 K 的最大子数组。

示例：我们有一个数组 A = [3,-5 1 2,-1 4,-3 1,-2]，我们想要找到长度最多为 K = 9 的最大子数组。子数组的长度不应受到限制在 K 处，如果存在另一个长度 L < K 提供更大的总和，则算法应返回 sum[:L]。

在这种情况下，算法将返回 0。在 A[2:5] 的总和之后，它应该返回 6。

Answer 1

好吧，在 O(n * K) 中有效的解决方案是对每个可能的长度 <= K 使用滑动窗口。我试图找到修改 Kadane 的 O(n) 正确解决方案，但我做不到。

def best_array_fixed_k( arr, length, k ):
    total_sum = 0
    best = 0
    for x in xrange( 0, length ):
        total_sum = total_sum + arr[x]
        if x >= k:
            total_sum = total_sum - arr[x - k]
        if x >= k - 1:
            best = max( best, total_sum )
            # this makes sure that we are considering a window with length = k
    return best

def max_sum( arr, length, k):
    best = 0
    for x in xrange( 1, k + 1):
        best = max( best, best_array_for_fixed_k(arr, length, x ) )
    return best