title: Is this the way the dynamic programming version of maximum subarray sum algorithm works?
body: <p>At the <code>dynamic programming</code> chapter in my algorithms textbook I have an example of how to solve the <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow">maximum sub array sum problem</a> using this technique. I am not sure if I got the idea behind the algorithm so I will describe here how I think it works (after reading several times about it and doing several examples).</p>
  
  <p>Basically, you have an array <code>A</code> of size <code>n</code>, and you want to find the maximum sub array sum of that array. The sub array with maximum sum can be somewhere in the right half of the array, left half, or somewhere in the middle. So you recursively call the function to compute the maximum sub array sum from the left and, then, from the right side of the array. Then, you compute the maximum sub array sum that from the middle of the array to the end, then compute the maximum sub array sum from the middle to the beginning of the array (it's length is not necessarily <code>n/2</code>). Then, if the sum of maximum sub array sum form left plus maximum sub array sum from the right is bigger than the maximum sub array sum from the left half (the one computed recursively ) and the maximum sub array sum from the right half (also computed recursively), then the maximum sub array sum is in the one in middle. Otherwise is the maximum of the one from left half and the one from right half (those were computed recursively).</p>
  
  <p>Did I got the working mechanism of the algorithm?</p>
  
  <p>This is the function that I was analyzing:</p>
  
  <pre><code>int maxSubArraySum(int* arr, int n)
  {
      if(n == 1)
      {
          return arr[0];
      }
      int m = n / 2;
      int left = maxSubArraySum(arr, m);
      int right = maxSubArraySum(arr + m, n - m);
      int leftsum = INT_MIN, rightsum = INT_MIN, sum = 0;
  
      for(int i = m; i &lt; n; i++)
      {
          sum += arr[i];
          rightsum = std::max(rightsum, sum);
      }
  
      sum = 0;
  
      for(int i = (m - 1); i &gt;= 0; i--)
      {
          sum += arr[i];
          leftsum = std::max(leftsum, sum);
      }
  
      int retval = std::max(left, right);
      return std::max(retval, leftsum + rightsum);    
  }  
  </code></pre>