628. Maximum Product of Three Numbers

题干：

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

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints:

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

这个题我觉得算法确实简单，Education里的解法也一眼就能懂。但是我不知道他们是怎么一下子就能想到用最大的三个数和最小的两个数以及最大的一个数的乘积去作比较的。

我只能从最Straight Forward的思路出发然后一步步推导这个过程

首先从最单纯的思路出发：
如果这是一个纯正数集合，那么只要取最大的三个数相乘即可。
如果这是一个含有正数和负数的集合，需要考虑的情况就变多了：

1. 负数个数 = 0，此时正数个数必然≥ 3，因此返回三个最大的正数相乘。
2. 负数个数== 1的情况
   1. 正数个数 == 2 (因为数列最少是3个) 三个数相乘返回
   2. 正数个数 >2 取最大的三个正数相乘。
3. 负数个数 == 2的情况
   1. 正数个数 == 1 时 三个数相乘返回
   2. 1 ≤ 正数个数 <3时 两个负数相乘再乘以最大的正数
   3. 正数个数≥3时 需要把两个负数相乘然后再乘以最大的正数，去和三个最大的正数比较谁最大。
4. 负数个数≥3的情况下
   1. 正数个数 == 0 三个最大的负数相乘返回
   2. 0< 正数个数≤ 1 取绝对值最大的两个负数相乘然后再乘以这个正数
   3. 1< 正数个数< 3 取绝对值最大的两个负数相乘然后再乘以最大的正数
   4. 正数个数≥3 取最小的两个负数（绝对值最大）相乘然后再乘以最大的正数，去和三个最大的正数比较谁最大。

基本上这就是全部情况了，直接这样写也不是不行但是很明显我们能从中找出一些规律。

比如当len(nums) == 3的时候直接返回数列相乘结果，如此一来我们可以合并2(a) 3(a)

同时，1和2(b)也可以合并

再看比较相似的 4(b), 4(c)以及 4(d) 3(c)

4(b), 4(c)明显可以合并，因为4(c)的计算方式是$smallest\_nagative1 \times smallest\_nagative2 \times max(positive)$ 而4(b)里只有一个正数因此max(positive) 就是那个数，因此我们可以合并这两个条件。

我们还可以合并 4(d) 3(c) ，对于4(d) 我们的算法大概是

return max(largest_positive1*largest_positive2*largest_positive3, largest_positive1*smallest_negative1*smallest_negative2)

当只有两个负数的时候很显然找到的最小的两个负数就是他们本身

合并之后我们可以把整个条件修改成这样

1. 只有三个数，那么三个数相乘返回
2. 负数个数 ≤ 1 且 正数个数≥ 3 取最大的三个正数相乘。
3. 负数个数 == 2 且1 ≤ 正数个数 <3时 两个负数相乘再乘以最大的正数
4. 负数个数≥2 且 正数个数≥3 时 取绝对值最大的两个负数相乘然后再乘以最大的正数，去和三个最大的正数比较谁最大。
5. 负数个数≥3的情况下
   1. 正数个数 == 0 取最大的三个数相乘返回
   2. 0< 正数个数< 3 取最小的两个负数（绝对值最大）相乘然后再乘以最大的正数

这样看起来就好写多了，但是我们是不是还能继续简化呢？明显还是有可以合并的条件。

首先1，2，5(a)可以合并。因为当负数个数 ≤ 1 且 正数个数≥ 3 取最大的三个正数也就是取最大的三个数，而只有三个数的时候取最大的三个数就是它们本身。

3和5(b)也明显可以合并，如此我们得到以下结果。

1. 只有三个数 或者 （负数个数 ≤ 1 且 正数个数≥ 3） 或者 （负数个数 ≥3且 正数个数 == 0）取最大的三个数相乘。
2. 负数个数 ≥ 2
   1. 1 ≤ 正数个数 <3时 两个负数相乘再乘以最大的正数
   2. 正数个数≥3 时 取最小的两个负数相乘然后再乘以最大的正数，去和三个最大的正数比较谁最大。

到了这一步更加明显了，我们无论什么条件，求的只有最小的两个负数和最大正数的乘积，或者最大的三个正数的乘积，或者最大的三个数的乘积而已。只是在没有这么多的正负数的情况下加入了一些判断条件。

在这里，最大的三个正数完全等同于最大的三个数，而最小的两个负数也等同于最小的两个数，于是我们可以消除正负号来看待这个问题。

如此便可以整理成下面的条件

1. 只有三个数 或者 （负数个数 ≤ 1 且 正数个数≥ 3） 或者 （负数个数 ≥3且 正数个数 == 0）取最大的三个数相乘。
2. 负数个数 ≥ 2
   1. 1 ≤ 正数个数 <3时 最小的两个数相乘再乘以最大的数
   2. 正数个数≥3 时 最小的两个数相乘然后再乘以最大的数，去和三个最大的数的乘积比较谁最大。

此时只要我们能合并2(a)和2(b)我们就能合并整个条件判断，因为1里面最大的三个数和最小的两个数相乘然后再乘以最大的数是一样的（largest1 * largest2 * largest3和smallest1 * smallest2 * largest1的值相等），可以用max(largest1 * largest2 * largest3, smallest1 * smallest2 * largest1)来计算。

而2(a)最大的三个数可以是正正负(乘积为负）或者正负（绝对值最小）负（绝对值第二小），因此用max(largest1 * largest2 * largest3, smallest1 * smallest2 * largest1)来计算一定会得到largest1 *smallest1 *smallest2

因此我们可以得出，在任何条件下，max(largest1 * largest2 * largest3, smallest1 * smallest2 * largest1)都是我们需要的结果。

因此答案也就呼之欲出了：

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        l = len(nums)
        return max(nums[l -1] * nums[l -2]* nums[l -3], nums[l -1] * nums[0]* nums[1])

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        l = len(nums)
        return max(nums[l -1] * nums[l -2]* nums[l -3], nums[l -1] * nums[0]* nums[1])

还有一个更为简单的办法：不需要排序，只需要循环一次，找到最小的两个数和最大的三个数即可。因为此题得出用最大的三个数乘积和最小的两个数*最大数相比较的思路最重要，所以只选择写出整个思路过程，不再纠结时间复杂度了。