title: Max. Product Dynamic Programming
body: <p>So I was trying to solve the <a href="http://www.geeksforgeeks.org/dynamic-programming-set-36-cut-a-rope-to-maximize-product/" rel="nofollow">Max. Product Question</a> and came up with the following recursion :</p>
  
  <pre><code> maxProd(n) = max of [k*(n-k),k*maxProd(n-k),maxProd(k)*(n-k),maxProd(k)*maxProd(n-k)]
  </code></pre>
  
  <p>However in the second solution given on that link they have skipped the maxProd(k)*maxProd(n-k).</p>
  
  <pre><code>int maxProd(int n)
  {
      // Base cases
      if (n == 0 || n == 1) return 0;
  
      // Make a cut at different places and take the maximum of all
      int max_val = 0;
      for (int i = 1; i &lt; n; i++)
        max_val = max(max_val, i*(n-i), maxProd(n-i)*i);
  
      // Return the maximum of all values
      return max_val;
  }
  </code></pre>
  
  <p>Is that still right? If so, how? Wouldn't it give wrong answers when the only way to get Max. Product is recursively split both k and n-k?</p>