LeetCode [628] Maximum Product of Three Numbers

 628. Maximum Product of Three Numbers

Easy

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

 

Example 2:

Input: [1,2,3,4]
Output: 24

 

Note:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

//1. (+)*(+)*(+): multiply the 3 max //2. (-)*(-)*(+): multiply the 2 min and 1 max //3. (-)*(-)*(-): there's no positive(otherwise it is case 2). multiply the 3 max //4. (-)*(+)*(+): there's one and only one negative(if more that one negative it is case 2; if no negative it is case 1). This negative must be included=>there are only 3 numbers. class Solution { public int maximumProduct(int[] nums) { int max1 = Integer.MIN_VALUE;//the largest int max2 = Integer.MIN_VALUE; int max3 = Integer.MIN_VALUE; int min1 = Integer.MAX_VALUE;//the smallest int min2 = Integer.MAX_VALUE; for(int i : nums){ if(i>max1){ max3=max2; max2=max1; max1 = i; }else if(i>max2){ max3 = max2; max2 = i; }else if(i>max3){ max3 = i; } if(i<min1){ min2 = min1; min1 = i; }else if(i<min2){ min2 = i; } } return Math.max(max1*max2*max3, min1*min2*max1); } }