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

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

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

<p>Here's my code in Python:</p>

<pre><code>def find(xs):
    neg_int = []
    pos_int = []
    if len(xs) == 1:
        return str(xs[0])
    for i in xs:
        if i &lt; 0:
            neg_int.append(i)
        elif i &gt; 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) &gt; 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 &gt; max_neg:
                max_neg = j
        neg_int.remove(max_neg)
    for k in neg_int:
        max = k*max
    return str(max)
</code></pre>

<p>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.</p>

<p>Now here's actual problem:
<a href="http://i.stack.imgur.com/zAw0f.png"><img src="http://i.stack.imgur.com/zAw0f.png" alt="enter image description here"></a></p>

<p>Here is another solution that doesn't require libraries :</p>

<pre><code>def find(l):
    if len(l) &lt;= 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 &lt; 0: # if the result is negative, remove biggest negative number and retry
        l.remove(max([e for e in l if e &lt; 0]))
        r = find(l)
    return r

print(find([-1, -2, -3, 0, 2])) # 12
print(find([-3, 0])) # 0
</code></pre>

<p><strong>EDIT :</strong></p>

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

python algorithm