如何在列表中找到两个元素的最大乘积？

Question

我在Hackerrank的比赛中尝试了一个有趣的问题，这是问题：

我使用了itertools，以下是代码：

import itertools

l = []

for _ in range(int(input())):
    l.append(int(input()))


max = l[0] * l[len(l)-1]

for a,b in itertools.combinations(l,2):
    if max < (a*b):
        max = (a*b)
print(max)

有没有比这更有效的方法？因为我在一些测试用例中遇到了超时错误，而我无法访问这些测试用例（因为这是一个小竞赛）。

- Maverick

---

你只需要找到两个最大的数并相乘吗？（如果允许负数，则还需找到两个最小的负数） - khelwood

@khelwood 我考虑过这个问题，但问题中明确写着不要依赖于“请记住答案并不总是两个最大数字的乘积。” 但我的主要问题是为什么会超时！ - Maverick

@Maverick 你可以通过检查负数来记住这一点。否则，你会为一个O(n)问题编写一个O(n^2)的解决方案。 - khelwood

@Maverick：问题中的提示是关于答案是两个最负数的乘积的情况。 - RemcoGerlich

itertools的时间复杂度为O(n^2)。 - User_Targaryen

Answer 1

遍历列表并找到以下内容：

最大正数(a)

第二大正数(b)

最大负数(c)

第二大负数(d)

现在，你将能够确定乘积的最大值，即 a*b 或 c*d

- User_Targaryen

---

很好的逻辑，我选择了使用heapq解决方案的答案。感谢你的回答。 - Maverick

Answer 2

只需对列表进行排序并选择列表中最后两个元素和前两个元素的乘积中最大的一个：

from operator import mul

numbers = [10, 20, 1, -11, 100, -12]
l = sorted(numbers)    # or sort in place with numbers.sort() if you don't mind mutating the list
max_product = max(mul(*l[:2]), mul(*l[-2:]))

这是一个O(n log n)的解决方案，由于排序原因。其他人建议使用heapq的解决方案，我发现对于超过几千个随机整数的列表来说，这个解决方案更快。

- mhawke

---

谢谢你的回答，但是那个heapq对于一些测试用例来说是合适的，所以必须加上标签。我也喜欢你的解决方案，它更简单。 - Maverick

@Maverick：没问题。它们基本上是等价的，但在某些情况下heapq会稍微快一些。 - mhawke

好算法。 - Fathy

Answer 3

以下是按照@User_Targaryen逻辑实现的代码。使用heapq函数返回列表中最大和第二大的数以及最小和第二小的数，使用mul operator函数计算这两对数字的乘积，然后使用max函数返回这两个乘积中的最大值。请注意，保留了HTML标签。

>>> import heapq
>>> from operator import mul
>>> l = [2,40,600,3,-89,-899]
>>> max(mul(*heapq.nsmallest(2,l)),mul(*heapq.nlargest(2,l)))
80011
# -899*-89 = 80011

- Chris_Rands

---

这个还不错，没有超时问题，但是在一个测试用例中仍然失败，不知道为什么。如果有人想尝试，请点击以下链接https://www.hackerrank.com/contests/arraysloops/challenges/arraysloops-4。 - Maverick

@Maverick 在阅读了这篇文章之后，我稍微编辑了我的答案，使用mul而不是lambda语法来实现返回一个列表的乘积。 - Chris_Rands

你不需要使用 reduce，尝试元组解包：max(mul(*heapq.nsmallest(2, l)), mul(*heapq.nlargest(2, l)))。这个 heapq 解决方案对于长列表比我的基于排序的解决方案更快。 - mhawke