Generative recursion to find the sublist with the maximum sum

Question

I am trying to solve a generative recursion problem in Python. The question is:

In a list that consists of integers, find the adjoining sublist which has the largest sum and return that sum.
For example, if the given list is [−2, 1, −3, 4, −1, 2, 1, −5, 4], the adjoining sublist which has the largest sum is [4, −1, 2, 1], which has a sum 6

I have to follow the given algorithm to solve find_max:

Split given list (at the midpoint) into two: L_left and L_right.
Return the maximum value of following 3:
- The maximum sum of any sublist resides entirely in L_left (using a recursive call to find_max).
- The maximum sum of any sublist resides entirely in L_right (using a recursive call to find_max).
- The maximum sublist that overlaps L_left and L_right; i.e.,
  - First: Find max sum of any sublist starting from the midpoint (towards the left) and ending at some point on the left of the midpoint
  - Second: Find the max sum of any sublist starting from the midpoint (towards the right) and ending at some point on the right of the midpoint
  - Finally: Add the two max sums.

I have 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 is able to solve for lists with length 2. How do I extend this to work for a list with more elements?

Can you define "adjoining sublist", becuase I don't understand how [1, 2, -1, 4] and an adjoining sublist of [−5, 1, 4, −2, 2, −1, 2, −3, 1, −3, 4]. As I understanding the adjoining sublist with the maximum value would be [1, 4, -2, 2, -1, 2] with a sum of 6. — Lennart Regebro
[1, 2, -1, 4] is not a sublist of [−5, 1, 4, −2, 2, −1, 2, −3, 1, −3, 4]. Is there a typo? — zneak
One hint when using recursion: the @memoize decorator helps wonders to make a recursion go faster since recursion is in general a bad idea, due to time consumption - if you are interested in it: wiki.python.org/moin/PythonDecoratorLibrary#Memoize i know thats not really an answer to your question, though it is an important remark to make — usethedeathstar
If you can afford to not use a divide and conquer solution, I'd honestly suggest this: stackoverflow.com/questions/15062844/maximum-sum-sublist — zneak

falsetru falsetru · Accepted Answer · 2013-07-09T08:26:56

You didn't consider following:

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

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 for 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:])
    ...

Generative recursion to find the sublist with the maximum sum

1 Answers