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].
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
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments