I am following the book 'Introduction to Algorithm' and use the algorithm given for making the program but the program is not working as expected.
probably the sum of previous function is adding to the new sum and thus it is printed I don't know how. When I put a single element list the output is as expected but when I put 2 or more element list say [2,3] I get output 4 which is not expected
def max_crossing_subarray(array,low,mid,high):
left_sum = -1000
sum_ar = 0
for i in range(mid, low-1, -1):
sum_ar = sum_ar + array[i]
if sum_ar>left_sum:
left_sum = sum_ar
max_left = i
right_sum = -1000
sum_ar = 0
for i in range(mid,high):
sum_ar = sum_ar + array[i]
if sum_ar>right_sum:
right_sum = sum_ar
max_right = i
return [max_left, max_right, left_sum + right_sum]
def max_subarray(array, low, high):
if low==high:
return [low, high, array[low]]
else:
mid = int((low + high)/2)
left_low, left_high, left_sum = max_subarray(array, low, mid)
right_low, right_high, right_sum = max_subarray(array,mid+1,high)
cross_low, cross_high, cross_sum = max_crossing_subarray(array,
low, mid, high)
if left_sum>=right_sum and left_sum>=cross_sum:
return [left_low, left_high, left_sum]
elif right_sum>=left_sum and right_sum>=cross_sum:
return [right_low, right_high, right_sum]
else:
return [cross_low, cross_high, cross_sum]
arr = [2,3]
ar= max_subarray(arr, 0, len(arr)-1)
print(ar)
When I input the list [2] I got the output [0, 0, 2] #[low, high, sum] but for [2,3] and [2,5] I got output as [0, 0, 4] and [1, 1, 5] respectively which is not as expected.
While calculating max crossing subarray, in second for statement range should start at mid + 1 and end at high + 1. Firstly mid element right now is added to both left and right sum, secondly you finish summing at element before the last one.