长度不超过 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 提供更大的和，算法应该 return sum[:L].

在这种情况下，算法将return 0。它应该return 6，遵循A[2:5]的总和。

Answer 1

好吧，在 O(n * K) 中有效的解决方案是对每个可能的长度 <= K 使用滑动 windows。我试图找到修改 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

长度不超过 k 的连续子序列的最大和

Maximum sum of contiguous sub-sequence with length at most k

dynamic-programming

sub-array

subsequence