Lewis - 1 year ago 94
Python Question

# Find the subset of a set of integers that has the maximum product

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:

1. If we have an even number of negative integers, multiply everything in both list and we have the answer.

2. If we have an odd number of negative integers, find the largest and remove it from the list. Then multiply everything in both lists.

3. 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:

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download