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.

 

---

 题目标签：Array, Math

　　题目给了我们一个nums array，要我们找到最大的三数乘积。

　　先让我们来看一下几个例子，假设下面的数字是从小到大排序，- 代表负数，+ 代表正数

　　a. + + + + +

　　　　答案：max1 * max2 * max3　　最大的三个数字乘积

　　b. - - + + + 　　

　　　　答案：在 max1 * max2 * max3 和 min1 * min2 * max1 里取大的，这里就需要比较一下两边的 2种情况了。

　　c. - - 0 + + 

　　　　答案：min1 * min2 * max1， 这里包括0，其实0并不会影响我们的算法。

　　d. - - - - +

　　　　答案：min1 * min2 * max1

　　e. - - - - -

　　　　答案：max1 * max2 * max3， 这里全部都是负数，答案反而变成了三个最大的数字乘积，因为这个情况下，总会是负数，所以要挑最右边三个数字。

 

　　这样我们就发现了，最大三个数字乘积，就发生在 最大的三个数字乘积 和 最小的2个数字 * 最大的数字 中。只要维护更新max1, max2, max3, min1, min2 取大的那种情况就可以。

 

 

 

Java Solution:

Runtime beats 91.55% 

完成日期：10/18/2017

关键词：Array, Math

关键点：维护更新max1, max2, max3, min1, min2

1 class Solution  2 { 3     public int maximumProduct(int[] nums)  4     { 5         int max1 = Integer.MIN_VALUE; 6         int max2 = max1; 7         int max3 = max1; 8          9         int min1 = Integer.MAX_VALUE;10         int min2 = min1;11         12         13         for(int num: nums)14         {15             // take care max16             if(num > max1)17             {18                 max3 = max2;19                 max2 = max1;20                 max1 = num;21             }22             else if(num > max2)23             {24                 max3 = max2;25                 max2 = num;26             }27             else if(num > max3)28                 max3 = num;29             30             31             // take care min32             if(num < min1)33             {34                 min2 = min1;35                 min1 = num;36             }37             else if(num < min2)38                 min2 = num;39         }40         41         42         return Math.max(max1 * max2 * max3, min1 * min2 * max1);                43     }44 }

参考资料：n/a

LeetCode 题目列表 - 

题目来源：https://leetcode.com/