title: Generative recursion to find the sublist with the maximum sum
body: <p>I am trying to solve a generative recursion problem in Python. The question is:</p>
  
  <ul>
  <li>In a list that consists of integers, find the adjoining sublist which has 
  the largest sum and return that sum. </li>
  <li>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</li>
  </ul>
  
  <p>I have to follow the given algorithm to solve find_max:</p>
  
  <ol>
  <li>Split given list (at the midpoint) into two: L_left and L_right.</li>
  <li>Return the maximum value of following 3: 
  <ul>
  <li>The maximum sum of any sublist resides entirely in L_left (using a recursive call to find_max). </li>
  <li>The maximum sum of any sublist resides entirely in L_right (using a recursive call to find_max). </li>
  <li>The maximum sublist that overlaps L_left and L_right; i.e., 
  <ul>
  <li>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</li>
  <li>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</li>
  <li>Finally: Add the two max sums.</li>
  </ul></li>
  </ul></li>
  </ol>
  
  <p>I have tried the following:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>This is able to solve for lists with length 2. How do I extend this to work for a list with more elements?</p>