数组中3个整数的最大乘积

Question

我试图解决一个问题，我想找到数组中任何3个整数的最大乘积。

我试过我的解决方案：

def maximumProduct(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    list_of_ints = nums

    t = sorted(list_of_ints[:4])

    max_pos = t[2] 
    max_pos_2 = t[1]
    max_pos_3 = t[0]

    min_neg = 0
    min_neg_2 = 0

    for x in list_of_ints[3:]:
        if x<0 and x< min_neg:
            temp = min_neg
            min_neg = x
            min_neg_2 = temp

        elif x<0 and x<min_neg_2: 
            min_neg_2 = x

        if x>0 and x>max_pos:
            temp = max_pos
            max_pos = x
            temp2 = max_pos_2
            max_pos_2 = temp
            max_pos_3 = temp2

        elif x>0 and x>max_pos_2:
            temp = max_pos_2
            max_pos_2 = x
            max_pos_3 = temp

        elif x>0 and x>max_pos_3:
            max_pos_3 = x

    return max(max_pos*max_pos_2*max_pos_3, min_neg*min_neg_2*max_pos)

输入nums = [-1, -2, -3]上面的解决方案失败了。预期的输出是-6，程序的输出是0。

这是由于min_neg和min_neg_1初始化为零。

如何初始化以避免此问题？我总是在设置正确的初始化时遇到问题。

Answer 1

Approach

要有效地解决这种运动，你需要认识到只有少数可能的情况。专注于数字的迹象，并思考结果的标志：

+ * + * + = +  (good)
+ * + * - = -  (bad)
+ * - * - = +  (good)
- * - * - = -  (bad)
anything * 0 = 0 (neutral)

因此，如果列表同时具有负数和负数，则答案是三个最大数字的乘积，或者是两个最小（负）数和最大数（正数）的乘积。

如果此条件不成立，则答案必须是数组中最大数字的乘积。

O(n log (n)) solution

因此，答案必须在排序后取出数组中的最后三个元素，或者取两个前一个元素和最后一个元素，然后将它们相乘。最简单和最优雅的方法是首先对数字列表进行排序：

def maximum_product(nums): # O(n log(n)) solution
   nums.sort()
   assert len(nums) >= 3 # assume the input has been validated
   a1 = nums[-1] * nums[-2] * nums[-3]
   a2 = nums[0] * nums[1] * nums[-1]
   return max(a1, a2)

O(n) solution

但是，您也可以在O（n）时间内找到最大三个和最小两个数字。如何在容器中找到最大N数字的一种有效方法是在迭代它时保持一堆大小为N。最后，堆包含答案：N最大元素的部分排序列表。

Python模块heapq为此提供convenient API：函数nlargest()和nsmallest()。所以我们走了：

import heapq

def maximum_product(nums): # O(n) solution
   assert len(nums) >= 3 # assume the input has been validated
   max3 = heapq.nlargest(3, nums)
   min2 = heapq.nsmallest(2, nums)
   a1 = max3[0] * max3[1] * max3[2]
   a2 = min2[0] * min2[1] * max(max3)
   return max(a1, a2)

Answer 2

您可以初始化为负无穷大：min_neg = float('-inf')

Answer 3

试试这个：

arr = sorted(list_of_ints)

def getMax(t):

    maxP = t[0] * t[1] * t[2]

    i = 0
    while t[i] > -1:
        i += 1

    maxN = t[i] * t[i + 1] * t[0]

    return max(maxP, maxN)

print(getMax(arr))

Answer 4

您可以使用itertools.combinations轻松完成。你称之为“数组”的东西在Python中被称为“列表”。

from itertools import combinations

def maximum_product(nums):
    return max(trio[0] * trio[1] * trio[2] for trio in combinations(nums, 3))

nums = [-1, -2, -3, 9]
print(maximum_product(nums))  # -> 54

这可以推广到通过（也）使用functools.reduce()计算N个项的乘积来确定N个整数的最大乘积：

from functools import reduce
from itertools import combinations

def maximum_product(nums, group_size):
    return max(reduce(lambda a, b: a*b, nums, 1)
                    for group in combinations(nums, group_size))

nums = [-1, -2, -3, 9]
print(maximum_product(nums, 3))  # -> 54

当然，这种普遍性会减慢执行速度......