Given an integer array arr[] , write a program to find three numbers in the array whose product is maximum and return the maximum product of these three numbers.

Problem Note

  • The array contains both +ve and -ve numbers.
  • The elements on the array can be non-contiguous.

Example 1 

Input: arr[] = [-5, -7, 4, 2, 1, 9]
Output: 315
Explanation: Max Product of 3 numbers = -5 * -7 * 9 = 315

Example 2 

Input: arr[]= [4, 5, -19, 3]
Output: 60
Explanation: Max Product of 3 numbers = 4 * 5 * 3 = 60