寻找一个整数集合的子集，使其乘积最大。

Question

让 A 为一组非空整数。编写一个名为“find”的函数，该函数输出 A 中具有最大乘积的非空子集。例如，find([-1,-2,-3,0,2]) = 12 =（-2）*（-3）* 2。

我的想法是将列表分为正整数列表和负整数列表:

1. 如果负整数个数为偶数，则将两个列表中的所有数字相乘即可得到答案。 2. 如果负整数个数为奇数，则找到最大的那个负整数并将其从列表中删除。然后将两个列表中的所有数字相乘。 3. 如果列表只有一个元素，则返回该元素。

以下是我在 Python 中编写的代码：

def find(xs):
    neg_int = []
    pos_int = []
    if len(xs) == 1:
        return str(xs[0])
    for i in xs:
        if i < 0:
            neg_int.append(i)
        elif i > 0:
            pos_int.append(i)
    if len(neg_int) == 1 and len(pos_int) == 0 and 0 in xs:
        return str(0)
    if len(neg_int) == len(pos_int) == 0:
        return str(0)
    max = 1
    if len(pos_int) > 0:
        for x in pos_int:
            max=x*max
    if len(neg_int) % 2 == 1:
        max_neg = neg_int[0]
        for j in neg_int:
            if j > max_neg:
                max_neg = j
        neg_int.remove(max_neg)
    for k in neg_int:
        max = k*max
    return str(max)

我有遗漏吗？附注：这是谷歌的foobar挑战中的一个问题，我似乎缺少一个案例，但我不知道是哪个。

现在是实际问题：

- user112358

---

我指的是数值上最大的负数，即-1 > -3。 - user112358

请执行 max_neg = abs(neg_int[0]).. 并基于绝对值进行比较。 - User_Targaryen

集合需要是最小尺寸的集合吗？例如，[2, 3, 1, 1] 的结果与 [2, 3] 相同。挑战中是否有关于如何解决这种差异的说明？ - mgilson

不，它不是一个集合，因为重复的值可以存在。从技术上讲，我应该这么说。 - user112358

@Lewis：在某些边缘情况下，你返回0而不是返回str(0)。请更改它。 - User_Targaryen

Answer 1

你可以使用reduce（在Py3的functools中）来简化这个问题。

import functools as ft
from operator import mul

def find(ns):
    if len(ns) == 1 or len(ns) == 2 and 0 in ns:
        return str(max(ns))
    pos = filter(lambda x: x > 0, ns)
    negs = sorted(filter(lambda x: x < 0, ns))
    return str(ft.reduce(mul, negs[:-1 if len(negs)%2 else None], 1) * ft.reduce(mul, pos, 1))

>>> find([-1, -2, -3, 0, 2])
'12'
>>> find([-3, 0])
'0'
>>> find([-1])
'-1'
>>> find([])
'1'

- AChampion

---

这个解决方案似乎在输入[-1]时会崩溃，并且不返回字符串。 - cdlane

好的，它没有涵盖所有特殊情况。添加了一个单一的保护程序。 - AChampion

Answer 2

from functools import reduce
from operator import mul

def find(array):
    negative = []
    positive = []
    zero = None
    removed = None

    def string_product(iterable):
        return str(reduce(mul, iterable, 1))

    for number in array:
        if number < 0:
            negative.append(number)
        elif number > 0:
            positive.append(number)
        else:
            zero = str(number)

    if negative:
        if len(negative) % 2 == 0:
            return string_product(negative + positive)

        removed = max(negative)

        negative.remove(removed)

        if negative:
            return string_product(negative + positive)

    if positive:
        return string_product(positive)

    return zero or str(removed)

- cdlane

Answer 3

以下是一个只需要一个循环的解决方案：

def max_product(A):
    """Calculate maximal product of elements of A"""
    product = 1
    greatest_negative = float("-inf") # greatest negative multiplicand so far

    for x in A:
        product = max(product, product*x, key=abs)
        if x <= -1:
            greatest_negative = max(x, greatest_negative)

    return max(product, product // greatest_negative)

assert max_product([2,3]) == 6
assert max_product([-2,-3]) == 6
assert max_product([-1, -2, -3, 0, 2]) == 12
assert max_product([]) == 1
assert max_product([-5]) == 1

额外加分：如果整数限制被放松，那怎么办？在循环期间需要收集哪些额外信息？

- Colonel Panic

Answer 4

这里有另一种不需要库的解决方案：

def find(l):
    if len(l) <= 2 and 0 in l: # This is the missing case, try [-3,0], it should return 0
        return max(l)
    l = [e for e in l if e != 0] # remove 0s    
    r = 1
    for e in l: # multiply all
        r *= e 
    if r < 0: # if the result is negative, remove biggest negative number and retry
        l.remove(max([e for e in l if e < 0]))
        r = find(l)
    return r

print(find([-1, -2, -3, 0, 2])) # 12
print(find([-3, 0])) # 0

编辑：

我认为我已经找到了缺失的情况，即当列表中仅有两个元素，且最高值为0时。

- Loïc

---

@Lewis 我也这么想，但我真的看不出是什么情况。我会继续寻找，这个问题很有趣 :) - Loïc

实际上，你的解决方案还有一个问题：find([0,-1)] 输出 1 而不是 0。 - user112358

@Lewis 哦，我刚刚编辑了我的解决方案，我以为这是缺失的情况。 - Loïc

我刚刚更新了问题。请查看描述中的图片。：） - user112358

当你给这段代码一个单独的负数find([-3])，它会返回1。 - cdlane