Generating recursion to find the maximum amount sublist

Question

I am trying to solve the generative recursion problem in Python. The question arises:

• In the list, which consists of integers, find the neighboring sub-list that has the largest amount and return this amount.
• For example, if the given list is [-2, 1, -3, 4, -1, 2, 1, -5, 4], then the neighboring subset that has the largest sum is [4, -1, 2, 1] which has a sum of 6

I have to follow this algorithm to solve find_max:

• Divide this list (at the midpoint) into two: L_left and L_right.
• Returns the maximum value of the following 3:
  • The maximum amount of any subscriptions is completely in L_left (using the find_max recursive call).
  • The maximum amount of any subscriptions is entirely in L_right (using the find_max recursive call).
  • The maximum subselect that overlaps L_left and L_right; those.
    • First: find the maximum amount of any sublist, starting from the middle (left) and ending at some point to the left of the midpoint.
    • Second: find the maximum amount of any sublist, starting from the middle (towards the right) and ending at some point to the right of the middle.
    • Finally: add the two maximum amounts.

I tried the following:

def find_max(L): length = len(L) mid_index = length/2 if length == 1: return L[0] else: left = find_max(L[0:(length/2)]) right = find_max(L[(length/2):length]) max_subset = max(left,right,left+right) return max_subset 

This can be solved for lists of length 2. How can I expand this to work for a list with a large number of elements?

Answer 1

You have not considered the following:

• another base case: L is []
• the left half and the right half should be consistent.
  • According to your code, if L is [2, -5, 3] , in the first left + right recursion, 5 will be returned.

---

 def find_max(L): length = len(L) mid_index = length/2 if length == 0: return 0 elif length == 1: return max(L[0], 0) left = find_max(L[:mid_index]) right = find_max(L[mid_index:]) left_half = right_half = 0 # to the left accum = 0 for x in L[mid_index-1::-1]: accum += x left_half = max(left_half, accum) # to the right accum = 0 for x in L[mid_index:]: accum += x right_half = max(right_half, accum) return max(left, right, left_half + right_half) assert find_max([]) == 0 assert find_max([-1]) == 0 assert find_max([1, 2, 3]) == 6 assert find_max([2, -5, 3]) == 3 assert find_max([-5, 1, 4, -2, 2, -1, 2, -3, 1, -3, 4]) == 6 

---

Without a loop:

 def sum_max(L, accum=0, max_value=0): if not L: return max_value accum += L[0] return sum_max(L[1:], accum, max(max_value, accum)) def find_max(L): ... left_half = sum_max(L[mid_index-1::-1]) right_half = sum_max(L[mid_index:]) ...