在任意大小的列表中查找三个整数的乘积的最大值

Question

我刚刚完成了这个练习题：

给定一个整数列表，返回任意三个整数相乘所得的最大乘积。 例如，如果列表是 [-10, -10, 5, 2]，我们应该返回 500，因为这是 -10 * -10 * 5。

我编写了以下代码，它似乎可以工作，但我觉得它可以更简单。有什么想法吗？

def maxProduct(lst):
    combo = []
    for i in range(0,len(lst)):
        for j in range(0,len(lst)):
            for k in range(0,len(lst)):
                if i != j and j != k and i != k:
                    x = sorted([lst[i]] + [lst[j]] + [lst[k]])
                    if x not in combo: 
                        combo.append(x)
    final = []
    for i in combo:
        result = 1
        for j in i:
            result = result * j
        final.append(result)
             
    return max(final)

Answer 1

采用类似的“强力”方法，您可以使用一些内置函数使其成为单行代码（以及一些导入）：

from itertools import combinations
from functools import reduce
from operator import mul
result = max(reduce(mul, p, 1) for p in combinations(arr, 3))

Answer 2

考虑到列表是整数，只有两种非退化的可能性：

1. 三个最大正整数。
2. 最大正整数和两个最小负整数。

对列表进行排序。

return max( values[-1] * values[-2] * values[-3],
            values[-1] * values[ 0] * values[ 1])

Answer 3

将

x = sorted([lst[i]] + [lst[j]] + [lst[k]])

更改为

x = sorted([lst[i], lst[j], lst[k]])

Answer 4

这是一种通用但非常快速的方法（

O(n)

对于小

k

）执行此操作（< 6ms for 100K elements and

k=3

）。

它是通用，因为如果您选择的话，您可以查找任何

k>0

值（偶数或奇数）的最大乘积，而不仅仅是

k=3

。

这个想法是寻找顶部

k

和底部

k

值（

hi

，分别为

lo

）。我们不使用排序 (

O(n log n)

)，而是使用

heapq

（

O(n)

，使用了两次）来查找

hi

和

lo

。

通常

hi

将具有最大的正值，而

lo

将具有最大的负值，但如果

hi

中存在负值或

lo

中存在正值，则它会起作用。然后我们在

k

列表

2k

中寻找

hi + lo

组合。

from itertools import combinations
from functools import reduce
from operator import mul
import heapq

def prod(lst):
    return reduce(mul, lst, 1)

def find_max_prod(lst, k):
    hi = heapq.nlargest(k, lst)
    lo = heapq.nsmallest(min(k, len(lst) - len(pos)), lst)
    return max((prod(vals), vals) for vals in combinations(hi + lo, r=k))

这还会返回产品及其贡献值（用于检查）：

>>> find_max_prod([-10, -10, 5, 2], k=3)
(500, (-10, -10, 5))

>>> find_max_prod([-10, -10, 7, 3, 1, 20, -30, 5, 2], k=3)
(6000, (-30, -10, 20))

>>> find_max_prod([-10, -10, 7, 3, 1, 20, -30, 5, 2], k=4)
(42000, (-30, -10, 20, 7))

速度

n = 100_000
lst = np.random.randint(-20, 20, size=n).tolist()

%timeit find_max_prod(lst, 3)
# 5.7 ms ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

注释

• 如果没有正数（或没有负数），它就有效：

  >>> find_max_prod([-1,-2,-1,-5], 3)
  (-2, (-1, -1, -2))
  
  >>> find_max_prod([5,6,7,8], 3)
  (336, (8, 7, 6))
  

• 它也适用于浮动：

  >>> lst = np.random.normal(size=n).tolist()
  ... lst[:4]
  [-1.2645437227178908,
   0.04542859270503795,
   -0.17997935575118532,
   -0.03485546753207921]
  
  >>> find_max_prod(lst, 3)
  (72.00185172194192,
   (-4.159094140171658, -4.145875048073711, 4.175694390863968))
  

Answer 5

您可以将问题分解为子问题并使用它：

highest_product_of_3： 迄今为止任何三个数字的最高乘积。

highest_product_of_2： 迄今为止任何两个数字的最高乘积。

lowest_product_of_2： 迄今为止任何两个数字的最低乘积（如果我们有两个大负数，可能会很有用）。

最高：迄今为止看到的最高数字。

最低：迄今为止看到的最低数字。

def highest_product_of_3(list_of_ints):
if len(list_of_ints) < 3:
    raise ValueError('Less than 3 items!')

# Initialize highest and lowest based on the first two elements
highest = max(list_of_ints[0], list_of_ints[1])
lowest = min(list_of_ints[0], list_of_ints[1])

# Initialize highest and lowest products of two
highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
lowest_product_of_2 = list_of_ints[0] * list_of_ints[1]

# Initialize the highest product of three
highest_product_of_3 = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]

# Iterate through the list starting from the third element
for i in range(2, len(list_of_ints)):
    current = list_of_ints[i]
    
    # Update highest_product_of_3
    highest_product_of_3 = max(
        highest_product_of_3,
        current * highest_product_of_2,
        current * lowest_product_of_2
    )
    
    # Update highest_product_of_2
    highest_product_of_2 = max(
        highest_product_of_2,
        current * highest,
        current * lowest
    )
    
    # Update lowest_product_of_2
    lowest_product_of_2 = min(
        lowest_product_of_2,
        current * highest,
        current * lowest
    )
    
    # Update highest
    highest = max(highest, current)
    
    # Update lowest
    lowest = min(lowest, current)

return highest_product_of_3

Answer 6

简单朴素的实现 (O(n3)):

import itertools

def max_product_of_three(values):
    return max(
        x * y * z
        for x, y, z in itertools.combinations(values, 3)
    )

您可以通过首先对值进行排序来改进这一点。

---

编辑：这是一个性能更高的 (O(n)) 解决方案

import heapq

def max_product_of_three(values):
    x, y, z = heapq.nlargest(3, values)
    a, b = heapq.nsmallest(2, values)

    return max(
        x * a * b,
        x * y * z
    )