查找具有最大产品的一组整数的子集(Find the subset of a set of integers that has the maximum product)

查找具有最大产品的一组整数的子集(Find the subset of a set of integers that has the maximum product) python

让A是一个非空集合的整数。 编写一个函数查找 ，输出具有最大产品的A的非空子集。 例如， find（[ - 1，-2，-3，0，2]）= 12 =（ - 2）*（ - 3）* 2

以下是我的想法：将列表分为正整数列表和负整数列表：

如果我们有偶数个负整数，则将这两个列表中的所有内容相乘，我们就得到了答案。 如果我们有一个奇数的负整数，找到最大并从列表中删除它。 然后将两个列表中的所有内容相乘。 如果列表只有一个元素，则返回此元素。

这是我在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)

我错过了什么？ PS这是Google的foobar挑战中的一个问题，我显然错过了一个案例，但我不知道是哪一个。

现在这是实际问题：

Let A be a non-empty set of integers. Write a function find that outputs a non-empty subset of A that has the maximum product. For example, find([-1, -2, -3, 0, 2]) = 12 = (-2)*(-3)*2

Here's what I think: divide the list into a list of positive integers and a list of negative integers:

If we have an even number of negative integers, multiply everything in both list and we have the answer. If we have an odd number of negative integers, find the largest and remove it from the list. Then multiply everything in both lists. If the list has only one element, return this element.

Here's my code in 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)

Am I missing anything? P.S. This is a problem from Google's foobar challenge, I am apparently missing one case but I don't know which.

Now here's actual problem:

最满意答案

这是另一个不需要库的解决方案：

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。

Here is another solution that doesn't require libraries :

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

EDIT :

I think I've found the missing case which is when there are only two elements in the list, and the highest is 0.

查找具有最大产品的一组整数的子集(Find the subset of a set of integers that has the maximum product) python

让A是一个非空集合的整数。 编写一个函数查找 ，输出具有最大产品的A的非空子集。 例如， find（[ - 1，-2，-3，0，2]）= 12 =（ - 2）*（ - 3）* 2

以下是我的想法：将列表分为正整数列表和负整数列表：

如果我们有偶数个负整数，则将这两个列表中的所有内容相乘，我们就得到了答案。 如果我们有一个奇数的负整数，找到最大并从列表中删除它。 然后将两个列表中的所有内容相乘。 如果列表只有一个元素，则返回此元素。

这是我在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)

我错过了什么？ PS这是Google的foobar挑战中的一个问题，我显然错过了一个案例，但我不知道是哪一个。

现在这是实际问题：

Let A be a non-empty set of integers. Write a function find that outputs a non-empty subset of A that has the maximum product. For example, find([-1, -2, -3, 0, 2]) = 12 = (-2)*(-3)*2

Here's what I think: divide the list into a list of positive integers and a list of negative integers:

If we have an even number of negative integers, multiply everything in both list and we have the answer. If we have an odd number of negative integers, find the largest and remove it from the list. Then multiply everything in both lists. If the list has only one element, return this element.

Here's my code in 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)

Am I missing anything? P.S. This is a problem from Google's foobar challenge, I am apparently missing one case but I don't know which.

Now here's actual problem:

最满意答案

这是另一个不需要库的解决方案：

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。

Here is another solution that doesn't require libraries :

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

EDIT :

I think I've found the missing case which is when there are only two elements in the list, and the highest is 0.