三个数的最大乘积

Question

我正在尝试解决来自Leetcode的问题，为了方便起见，将其复制在这里

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:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

在尝试（不成功）后，我谷歌了解决方案，这个方法有效。

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = pa = pb = pc = None
        na = nb = 0x7FFFFFFF
        for n in nums:
            if n > pa:
                pa, pb, pc = n, pa, pb
            elif n > pb:
                pb, pc = n, pb
            elif n > pc:
                pc = n
            if n < na:
                na, nb = n, na
            elif n < nb:
                nb = n
        return max(ans, pa * na * nb, pa * pb * pc)

我理解这段逻辑，除了为什么na和nb被赋值为0x7FFFFFFF。看起来它是int32的最大值。有人能帮我解释一下这个数字的意义以及为什么在这里使用它吗？（我本来会使用1001代替）

- user1596115

---

为什么ans从未改变其初始常量值？我认为0x7FFF_FFFF除了是最大可能的数字之外没有任何意义，因此保证被数组中的数字覆盖。它比1001更好，因为即使是那些没有正确阅读问题描述的人也能看到它是最大可能的数字。我想这就是全部。 - user234461

代码看起来也像是由Java程序员编写的；这个类没有任何作用。 - chepner

基本上，答案来自三种情况之一：最大的三个正数、最大的三个负数或最大的两个负数和最大的正数。 na 和 nb 只是初始化为某个无限版本，以使比较第一次起作用。 - chepner

@chepner 谢谢您的回复，LeetCode 给出了预期代码的基本框架，因此需要使用类。然而，我同意它没有任何作用。 - user1596115

Answer 1

在伪代码中，0x7FFFFFFF会被渲染为无穷大（而None则是负无穷）。正确性的证明是一个引理，即最大的三个数可以在最大的三个数和最小的两个数中找到。正/负无穷充当min/max两个/三个值的哨兵值，一旦扫描了前三个值，就会很快被实际值替换。 1001同样适用。

- David Eisenstat

Answer 2

除了@David Eisenstat的答案外，还有几点补充：

- 将`None`视为负无穷是在Python2中有效的，但在Python3中会引发异常，例如：

``` 在早期版本的Python中，决定比较任意两个对象是合法的，并且将返回一致的结果。因此，不同类型的对象将根据它们的类型（一个实现相关的、未指定但一致的排序）进行比较，而相同类型的对象将根据适用于该类型的规则进行比较。 其他实现有权以不同的方式比较整数和None，但在特定实现上，结果不会改变。 Python 3将在这些比较中引发异常。 ```

- 您是正确的，`0x7FFFFFFF`将等同于最大的有符号整数，即`sys.maxsize == 0x7FFFFFFF` - 在Python2中，您可以进行以下比较：`0x7FFFFFFF > (1000*1000*1000)` 和 `None < -(1000*1000*1000)` 都是`True`，因此使用`0x7FFFFFFF`作为上限，`None`作为下限也是可以的，尽管其他边界也是正确的 - 话虽如此，我建议您重构该代码，使其在Python3中也能正常运行 :)

- BPL

Answer 3

考虑以下示例：[-999，-999，100，200，300]，答案是采取-999，-999和300（而不仅仅是三个最大数字的乘积）。

因此，您需要存储：

- 三个最大的数字（pa、pb、pc） - 两个最小的数字（na、nb）

结果是pa * na * nb和pa * pb * pc之间的最大值。

0x7FFFFFFF只是一个用于查找最小值的非常大的数字。由于最大可能的值为1000，因此可以使用1000代替。

同样，作者使用None初始化pa、pb和pc。作者可以使用-1000代替。

- Maxime Chéramy

Answer 4

虽然这并没有真正提供实际问题的答案，但这是一个替代方案，绕过了提出的场景，并实现了相同（最终）目标（更优雅，但对于大型列表来说速度较慢）。
它适用于Python 2和Python 3（其中reduce也可以被itertools.accumulate替换），并使用了：

• [Python 2.Docs]：内置函数（max，reduce）
• [Python 2.Docs]：operator-作为函数的标准运算符（mul）
• [Python 2.Docs]：itertools-创建有效循环迭代器的函数（combinations）

>>> import itertools
>>> import operator
>>> 
>>> l = [1, 9, 0, -5, 7, 2, 4]
>>>
>>> def max_prod(seq, count=3):
...     return max(reduce(operator.mul, item) for item in itertools.combinations(seq, count))
...
>>> max_prod(l)
252

即： 9 * 7 * 4。

- CristiFati

---

我认为你也应该说，如果列表很大，则更优雅但速度较慢。然而，该语句表明列表的长度低于104，因此完全可以接受（少于200,000个组合）。 - Maxime Chéramy