Lewis - 4 months ago 27

Python Question

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:

Answer

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.