NC106 三个数的最大乘积

描述： 给定一个长度为 nn 的无序数组 AA ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度： O(n) ，空间复杂度： O(1) 。

数据范围：3≤n≤10^4，-10^4≤A[i]≤10^4

思路：数组的情况分为全正数，全负数，正数+负数，正数+0，0+负数，正数+0+负数。如果数组长度为3，直接全部相乘，

全正数：最大的3个数相乘（3大）。

全负数：3大。

正数+负数：可能是一正n（n>=3)负，两正n(n>=2)负，三正n(n>=1)负。

  1. 一正的情况，结果为一正两负相乘（1大2小）。
  2. 两正的情况，情况同一正。
  3. 三正n(n>=1)负，结果为三正（3大）或一正两负（1大2小）

正数+0：3大

负数+0：3大

正数+0+负数：

  1. 一正：若只有一个负数，则一正数、N个0、一负数，则结果为0，3大相乘为0，1大2小相乘也为0。若负数个数>=2，则结果为一正两负（1大2小）
  2. 两正：情况同一正
  3. 三正：结果为三正（3大）或一正两负（1大2小）

总结：最后的结果要么是3大，要么是（1大2小），所以只需要遍历一遍，找出3大和1大2小，然后比较3大乘积和1大2小的乘积（其中都有最大值，所以比较第2大*第3大与最小的两个数的乘积），谁更大就返回谁。

方法不难，就是梳理各种情况，弄得我头疼，我之前老纠结0的问题，代码的if写了一堆，之前还把数组分成正负，正数取最大的三个值，负数取最大的3个值和最小的2个值，后来发现，其实情况就两种，需要的值并没有那么多。可以直接用两个数组存数据，一个存最大的三个值，一个存最小的两个值，然后乘积比较。我这写得还复杂一点。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大乘积
# @param A int整型一维数组 
# @return long长整型
#
class Solution:
    def solve(self , A: List[int]) -> int:
        # write code here
        arr = {'max1':0,'max2':0,'max3':0,'min1':0,'min2':0}
        if len(A) == 3:
            return A[0]*A[1]*A[2]
        for i in A:
            if (arr['max1'] == 0) | (i > arr['max1']):
                arr['max3'] = arr['max2']
                arr['max2'] = arr['max1']
                arr['max1'] = i
            elif (arr['max2'] == 0) | (i > arr['max2']):
                arr['max3'] = arr['max2']
                arr['max2'] = i
            elif (arr['max3'] == 0) | (i > arr['max3']):
                arr['max3'] = i
            if (arr['min1'] == 0) | (i < arr['min1']):
                arr['min2'] = arr['min1']
                arr['min1'] = i
            elif (arr['min2'] == 0) | (i < arr['min2']):
                arr['min2'] = i
        if arr['max2'] * arr['max3'] < arr['min1'] * arr['min2']:
            return arr['max1'] * arr['min1'] * arr['min2']
        else:
            return arr['max1'] * arr['max2'] * arr['max3']