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