题目

难度：★★☆☆☆
类型：数组

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

注意
给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

示例

示例 1:
输入: [1,2,3]
输出: 6

示例 2:
输入: [1,2,3,4]
输出: 24

解答

这里首先给出一个定理：数组中的最大三数之积是【数组中三个最大值之积】与【数组最大值与两个最小值之积】的最大值。

证明，考虑以下几种情况：

如果数组中的数字个数不超过3个，则不存在三数之积；

如果数组中的数组个数恰好等于三个，则数组中所有元素之积即为三数之积；

如果数组中元素个数超过三个，考虑以下情况：
（1）数组中的元素全为正数，则数组中最大的三数之积为数组中三个最大数字的乘积（max_1max_2max3）；
（2）数组中的元素全为负数，三数之积一定也是负数，则我们希望三数之积的绝对值最小，换句话说，如果我们把数组中的所有数取相反数，我们的问题就变成了获得正数数组的最小三数之积，而正数数组的最小三数之积实际上是最小值与两个最大值的乘积，那么原数组的最大三数之积等于最大值与两个最小值之间的乘积(min_1min_2max_1)；
（3）数组中既有正数又有负数，有两种情况，如果负数个数只有一个，那么正数个数至少有三个，这时的最大三数之积就与情况（1）一致，另外，如果负数有不少于两个，两个负数乘积获得正数，再与最大的正数乘积后有可能比情况（1）的计算方式还要大，因此我们取两种计算方式的最大值即可。零的存在对以上判断过程没有影响，感兴趣的读者可以自行证明。

问题转化为如何获得数组中的这5个数字：最大值（max_1）、次大值（max_3）、第三大值（max_3）、最小值（min_1）、次小值（min_2），这里给出两种方法，供读者参考。

方案1：排序

class Solution(object):
    def maximumProduct(self, nums):
        nums.sort()
        return max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1])

方案2：遍历

class Solution(object):
    def maximumProduct(self, nums):
            max_1, max_2, max_3 = -1001, -1001, -1001   # 寻找前三大数
            min_1, min_2 = 1001, 1001                   # 寻找后两小数
            for i in range(len(nums)):                  # 遍历数组
                if nums[i] > max_1:                     # 发现最大数并更新变量
                    max_3 = max_2
                    max_2 = max_1
                    max_1 = nums[i]
                elif nums[i] > max_2:                   # 发现第二大数并更新变量
                    max_3 = max_2
                    max_2 = nums[i]
                elif nums[i] > max_3:                   # 发现第三大数并更新变量
                    max_3 = nums[i]

                if nums[i] < min_1:                     # 发现最小数并更新变量
                    min_2 = min_1
                    min_1 = nums[i]
                elif nums[i] < min_2:                   # 发现第二小数并更新变量
                    min_2 = nums[i]
            return max(max_3*max_2*max_1, min_1*min_2*max_1)

如有疑问或建议，欢迎评论区留言~