title: Max Sum Subarray - Divide and Conquer
body: <p>I created a recursive function that takes in an array of ints, and returns the sum of the continuous subarray with the largest sum. </p>
  
  <p>Example:</p>
  
  <p>input: 1 4 -9 8 1 3 3 1 -1 -4 -6 2 8 19 -10 -11</p>
  
  <p>subarray: 8 1 3 3 1 -1 -4 -6 2 8 19</p>
  
  <p>sum: 34</p>
  
  <p>My algorithm is a little off. About 2/3's of my test inputs are wrong. A list of my tests is below the code. </p>
  
  <pre><code>def max_sum_subarray(arr, left, right):
  
      maxLeftBorderSum = 0
      maxRightBorderSum = 0
      leftBorderSum = 0
      rightBorderSum = 0
      center = (left + right)/2
  
      if left == right:
          return arr[left]
  
      maxLeftSum = min_sum_subarray(arr, left, center)
      maxRightSum = min_sum_subarray(arr, center+1, right)
  
      for i in range(center, left, -1):
          leftBorderSum = leftBorderSum + arr[i]
          if leftBorderSum &gt; maxLeftBorderSum:
              maxLeftBorderSum = leftBorderSum
  
      for i in range(center+1, right):
          rightBorderSum = rightBorderSum + arr[i]
          if rightBorderSum &gt; maxRightBorderSum:
              maxRightBorderSum = rightBorderSum  
  
      return max(maxLeftBorderSum + maxRightBorderSum, max(maxRightSum, maxLeftSum))
  </code></pre>
  
  <p>Some tests:</p>
  
  <pre><code>1 4 -9 8 1 3 3 1 -1 -4 -6 2 8 19 -10 -11
  </code></pre>
  
  <p>Correct Answer = 34<br>
  My answer = 34</p>
  
  <pre><code>2 9 8 6 5 -11 9 -11 7 5 -1 -8 -3 7 -2
  </code></pre>
  
  <p>Correct Answer = 30<br>
  My answer = 28</p>
  
  <pre><code>10 -11 -1 -9 33 -45 23 24 -1 -7 -8 19
  </code></pre>
  
  <p>Correct Answer = 50<br>
  My answer = 47</p>
  
  <pre><code>31 -41 59 26 -53 58 97 -93 -23 84
  </code></pre>
  
  <p>Correct Answer = 187<br>
  My answer = 187</p>
  
  <pre><code>3 2 1 1 -8 1 1 2 3
  </code></pre>
  
  <p>Correct Answer = 7<br>
  My answer = 4</p>
  
  <pre><code>12 99 99 -99 -27 0 0 0 -3 10
  </code></pre>
  
  <p>Correct Answer = 210<br>
  My answer = 198</p>
  
  <pre><code>-2 1 -3 4 -1 2 1 -5 4
  </code></pre>
  
  <p>Correct Answer = 6<br>
  My answer = 6</p>