title: Find maximum product of 3 numbers in an array
body: <p>Given an array of integers, which can contain both +ve and -ve numbers. I've to maximize the product of any 3 elements of the array. The elements can be non-contiguous. </p>
  
  <p>Some examples:</p>
  
  <pre><code>int[] arr = {-5, -7, 4, 2, 1, 9};  // Max Product of 3 numbers = -5 * -7 * 9
  int[] arr2 = {4, 5, -19, 3};       // Max Product of 3 numbers = 4 * 5 * 3
  </code></pre>
  
  <p>I've tried solving it using <em>Dynamic Programming</em>, but I'm not getting the expected result. It is returning the result often involving the same number twice in the multiplication. So, for the array - <code>{4, 2, 1, 9}</code>, it is returning - <code>32</code>, which is <code>4 * 4 * 2</code>. </p>
  
  <p>Here's my code:</p>
  
  <pre><code>public static int maxProduct(int[] arr, int count) {
      return maxProduct(arr, 0, arr.length - 1, count);
  }
  
  private static int maxProduct(int[] arr, int fromIndex, int toIndex, int count) {
  
      if (count == 1) {
          return maximum(arr, fromIndex, toIndex);
      } else if (toIndex - fromIndex + 1 &lt; count) {
          return 1;
      } else {
          return MathUtil.max(maxProduct(arr, fromIndex, toIndex - 1, count - 1) * arr[toIndex - 1], 
                              maxProduct(arr, fromIndex, toIndex - 1, count));
      }
  }
  </code></pre>
  
  <ul>
  <li><code>MathUtil.max(int a, int b)</code> is a method that gives maximum of <code>a</code> and <code>b</code>.</li>
  <li>The two values I pass to <code>max</code> method there are: 
  <ul>
  <li><code>maxProduct</code>, when we consider last element as a part of product.</li>
  <li><code>maxProduct</code>, when we don't consider it as a part of product.</li>
  </ul></li>
  <li><code>count</code> contains the number of element we want to consider. Here <code>3</code>.</li>
  <li>For <code>count == 1</code>, we have to find maximum of 1 element from array. That means, we have to use maximum array element.</li>
  <li>If <code>toIndex - fromIndex + 1 &lt; count</code>, means, there are not enough elements in the array between those indices.</li>
  </ul>
  
  <p>I've an intuition that, the first <code>if</code> condition is one of the reason of failure. Because, it is only considering maximum element from an array, while the maximum product may comprise of negative numbers too. But I don't know how to take care of that.</p>
  
  <p>The reason I'm using Dynamic Programming is that I can then generalize this solution to work for any value of <code>count</code>. Of course, if someone have any better approach, even for <code>count = 3</code>, I welcome the suggestion (I would want to avoid sorting the array, as that will be another <code>O(nlogn)</code> at the least).</p>