Find the max product value of 3 number
from the given array .
For example , if array has
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] find the max product from three
numbers. max_product(x*x*x)
We need to consider following cases
a. what if array has only -ves.
b. what if array has only +ves.
c. what if array has 0.
What if array has both +ves and -ves
Sort array,
a. Compute initial product has last three
elements in the array.
b. If array has more than 1 -ve values,
take first 2 negatives and last positive compute product. If this product is
greater than what we computed in step a, update maximum product.
import java.util.Arrays; import java.util.Objects; public class ArrayUtil { public static int maxProduct(int arr[]) { if (Objects.isNull(arr)) { throw new NullPointerException("Array shouldn't be null"); } if (arr.length < 3) { throw new IllegalArgumentException( "Array should have atleast 3 elements"); } Arrays.sort(arr); int length = arr.length; int maxProduct = arr[length - 1] * arr[length - 2] * arr[length - 3]; if (arr[0] < 0 && arr[1] < 0) { int tmpProduct; if (arr[length - 1] >= 0) { tmpProduct = arr[0] * arr[1] * arr[length - 1]; } else { tmpProduct = arr[length - 1] * arr[length - 2] * arr[length - 3]; } if (maxProduct < tmpProduct) return tmpProduct; } return maxProduct; } }
import static org.junit.Assert.assertEquals; import org.junit.Test; public class ArrayUtilTest { @Test public void test() { int arr1[] = { -1, 2, 3, -4, -5, -2, -8, -4 }; int arr2[] = { 1, -1, -2, 4, -5 }; int arr3[] = { 3, 2, 0, 1, 4, 5 }; int arr4[] = { 5, 4, 3, 0, -10, -20 }; int arr5[] = { -5, -4, 1, 2, 3, 4, 5, 6, 7 }; assertEquals(ArrayUtil.maxProduct(arr1), 120); assertEquals(ArrayUtil.maxProduct(arr2), 40); assertEquals(ArrayUtil.maxProduct(arr3), 60); assertEquals(ArrayUtil.maxProduct(arr4), 1000); assertEquals(ArrayUtil.maxProduct(arr5), 210); } }
No comments:
Post a Comment