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

Question

I am trying to modify the Kadane Algorithm in order to solve a more specific problem.

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

This is the code for the maximum subarray problem. What I want to do is find the maximum subarray with length at most K.

Example: We have an array A = [3,-5 1 2,-1 4,-3 1,-2] and we want to find the maximum subarray of length at most K = 9. Length of subarray should not be restricted at K, if there is another length L < K that provides a greater sum, the algorithm should return sum[:L].

In this case, the algorithm will return 0. It should return 6, following the sum of A[2:5].

Answer 1

Well, a solution that works in O(n * K) is to use sliding windows for every possible length <= K. I have tried to find a O(n) correct solution modifying Kadane, but I couldn't.

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