力扣(LeetCode)之三个数最大乘积

题目：

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

示例：

输入：nums = [1,2,3,4]
输出：24

输入：nums = [-1,-2,-3]
输出：-6

分析题目：这个题目中我们需要考虑三种情况：全为正数、全为负数、有正有负

• 全为正数：我们仅需要取出最大的三个数进行乘积。
• 全为负数：与上述一致，我们仅需要取出最大的三个数进行乘积。
• 有正有负：我们需要取出最大的正数，还有最小的两个负数，求这三个数的最大值。
  这样我们就能够求出一个整数数组中的三个数的最大乘积。

方法一：排序后再求结果

我们可以首先将数组进行排序，然后对相对应的值进行乘积，这样算法的复杂度完全取决于排序算法的复杂度了 。下面是该算法的实现：

# 先排序后比较大小
def fun1(arr):
    l = len(arr)
    arr =  sorted(arr) # 从小到大
    return max(arr[l-1]*arr[l-2]*arr[l-3], arr[0]*arr[1]*arr[l-1])

方法二：直接求取三个数相乘的最大值

这个算法的时间复杂度就是 ，我们仅需要将数组循环一遍就能够将最大值，最小值求出来，最后比较大小即可，具体算法如下：

# 求取最大最小值
def fun2(arr):
    min1 = float('inf')
    min2 = float('inf')
    max1 = -float('inf')
    max2 = -float('inf')
    max3 = -float('inf')
    for i, x in enumerate(arr):
        if x < min1:
            min2 = min1
            min1 = x
        elif x < min2:
            min2 = x 
        
        if x > max1:
            max3 = max2 
            max2 = max1 
            max1 = x 
        elif x > max2:
            max3 = max2 
            max2 = x
        elif x > max3:
            max3 = x 
    return max(max1*max2*max3, max1*min1*min2)