Maximizing the boolean combination of given real numbers
Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:


set $b_i=1$ if $x_i &gt; 0$
set $b_i=0$ if $x_i &lt; 0$
all others $b_i$ can either be zero or one


It is clear that any other assignment will give you a lower value (either by adding a positive value or not adding a positive one). If $|\{i:x_i=0\}|=K$, then you have $2^K$ solutions. This can be settled in $O(n)$ by a simple linear scanning of $x_i$ values (even less if they are ordered).