This is my solution to findMaximumSubarray, I follow CLRS Pseudo code algorithm and I get this recursion error I tried to figure out why, but I reach nothing !
I can't understand this part of recursion, the first line is to find divide left array until reaching the base case which is one element, then my brain is blowing I can't imagine what after that !
leftLow, leftHigh, leftSum = FindMaxSubarray(array, low, mid)
rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
crossLow, crossHigh, crossSum = MaxCrossSubarray(array, low, mid, high)
this is the whole code.
array = [0,1,-2,3,4,-2, 5, -1, 10, -2 ,11,9, -5, -10, 12]
low = 0
high = len(array)
mid = len(array)//2
def MaxCrossSubarray(array, low, mid, high):
sum = 0
left_sum = float('-inf')
for i in range(mid, low, -1):
sum = sum+array[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = float('-inf')
sum = 0
for i in range(mid+1, high):
sum = sum+array[i]
if sum > right_sum:
right_sum = sum
max_right = i
return (max_left, max_right, left_sum+right_sum)
def FindMaxSubarray(array, low, high):
if high == low :
return (low, high, array[low])
else:
mid = (high+low)//2
leftLow, leftHigh, leftSum = FindMaxSubarray(array, low, mid)
rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
crossLow, crossHigh, crossSum = MaxCrossSubarray(array, low, mid, high)
if leftSum >= rightSum and leftSum >=crossSum:
return (leftLow, leftHigh, leftSum)
elif rightSum >= leftSum and rightSum >=crossSum:
return (rightLow, rightHigh, rightSum)
else:
return (crossLow, crossHigh, crossSum)
low, high, sum = FindMaxSubarray (array, low, high)
leftLow, leftHigh, leftSum = FindMaxSubarray(array, low, mid)
rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
crossLow, crossHigh, crossSum = MaxCrossSubarray(array, low, mid, high)
The idea in the above code is that you are finding the max of subarray to the right, left and crosssum of the array. As you explained in the question the first line is to find divide left array until reaching the base case which is one element. This is correct and the same logic applies to the other parts.
The recursive issue is stemming from this line
rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
Where mid=0 and high = 1And this then causes the recursive error since under these values the following would always be false.
if high == low :
return (low, high, array[low])
To solve the recursive issue, simply change to this
rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid+1, high)
This ensures that a return condition can be met and so prevents the recursive error.
Having changed that it seems like your MaxCrossSubArray is not logically correct and gives the following error upon running it
UnboundLocalError: local variable 'max_right' referenced before assignment
Look into and see if you can solve it.
N.B: The CLRS is known to contain some errors and it is relatively old. So I would advise you to not stick with the same solution but look for other possibilities. See this for example.