Maximum product quadruple in an array

You are given an array, you are asked to find the maximum product quadruple in the array, i.e. the largest product that can be obtained by multiplying four numbers in the array.

Examples:

1. Input: [ 11 ,3 ,5 ,6 ,23 ,1 ]
   Output: 7590 ( 11 X 23 X 5 X 6)
2. Input: [ -10, -35, 2 ,3, 45 ,5 ]
   Output: 78750 ( -10 X -35 X 45 X 5 )

Now that you’ve found out the simplest way, is there a way the process can be optimised because of the time complexity of  $O\left(n^4\right)$?
A better way would be to sort the array, and then have 3 integer variables, x, y, z, storing the values of - 

x: Product of first two and last two elements of the array - arr[0]*arr[1]*arr[n-2]*arr[n-1]
y: Product of the last four elements of the array - arr[n-4]*arr[n-3]*arr[n-2]*arr[n-1]
z: Product of the first four elements of  the array - arr[0]*arr[1]*arr[2]*arr[3]

then you compare x, y, z, and return the maximum.

Once the array is sorted, it is not necessary that the last four numbers of the array would give the maximum product always. There may be some negative numbers whose absolute value is greater than the last four numbers. In such cases, the product of 4 negative numbers or 2 negative and 2 positive numbers can result in the maximum product. See the below example for better understanding.

Example:

Suppose the array is {10,20,30,40,50,60,70,80,-90,-100}, then the sorted array will be {-100,-90,10,20,30,40,50,60,70,80}

x = -100*-90*70*80 = 50400000

y = -100*-90*10*20 = 180000

z = 50*60*70*80 = 16800000

As already mentioned, you can compare x, y, z values and return the maximum.

Till now you have seen how to get the required quadruple using the brute force approach in O($n^4$) time complexity, then we tried to minimise the time complexity to O(n log n) by sorting the array and then applying some logic.

Another efficient approach is solving the problem in O(n) time complexity by simply traversing the array and while traversing, maintain eight variables, four to maintain the first four maximum elements of the array and four to maintain the first four minimum elements, and then calculate the following:

      x = firstMax * secondMax * thirdMax * fourthMax.

      y = firstMin * secondMin * thirdMin * fourthMin

      z = firstMin * secondMin * firstMax * secondMax

Maximum of x, y, z is the required answer.