title: solve maximum product of three array elements without sorting
body: <p>There is a variety of answers for the MaxProductOfThree task on <a href="https://codility.com/" rel="noreferrer">codility.com</a>, most of them involving a sorting algorithm.</p>
  
  <p>The problem is:</p>
  
  <p>A non-empty zero-indexed array A consisting of N integers is given.</p>
  
  <p>The problem is to find the maximum product of 3 elements from given array.</p>
  
  <p>The length of the array is between 3 and 100,000</p>
  
  <p>each element of array A is an integer within the range [−1,000..1,000]</p>
  
  <pre><code>    expected worst-case time complexity is O(N*log(N));
  
      expected worst-case space complexity is O(1), 
  </code></pre>
  
  <p>beyond input storage (not counting the storage required for input arguments).
  Example:</p>
  
  <pre><code>  a[0] = -3;
    a[1] = 7;
    a[2] = 2;
    a[3] = 1;
    a[4] = 5;
    a[5] = 7;
  </code></pre>
  
  <p>the max product is a[1]*a[4]*a[5] = 245</p>
  
  <p>Is there a linear-time solution to this problem, besides the O(n log n) approach that involves sorting?</p>