# Partition a list of positive and negative numbers into sets

Given a list of $L$ integers, containing positive and negative number,how do I partition them into $K$ sets such that majority of elements in it are positive. There are two cases in it :

1. When $K$ is odd.

2. When $K$ is even.

Now the majority of elements are considered to be positive when more than half of the elements in are positive. For simplicity, the cardinality of each set ($M$) is odd. ($L=K*M$).

Now we can take only the sign of integers i.e. represent positive with $+1$ and negative with $-1$. The elements in the set are to be consecutive so we make our list circular.

Instead of going through every possible consecutive sets, is there a efficient way to make those sets such that atleast $K/2$ are positive sets ?

Eg - 1. $K$ (odd)= $3$

$1 1 1 -1 1 -1 -1 1 -1$

One way : {$2,3.4$}, {$5,6,7$} , {$8,9,1$}

$2$ positive, $1$ negative so majorly positive

1. $K$ even= $4$

$-1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1$

There is no way possible to it to be major positive.

EDIT : How can we even tell if there is majority of positive sets ?

• How do you propose to do this if only one of your integers is positive, and the other $L-1$ are all negative? – Gerry Myerson Feb 13 '17 at 10:56
• @GerryMyerson Then we simply it's not possible or rather say it is the list of majority negative sets. – Buckster Feb 13 '17 at 10:59
• Work through the list, closing a partition as soon as it has one more positive than negative numbers in it. This gives you the maximum number of predominantly positive partitions. – Thumbnail Feb 13 '17 at 11:14
• @Thumbnail I get the idea but every $K$ set has to have exactly $M$ integers in it. Also the way has to be efficient and optimized further. – Buckster Feb 13 '17 at 11:19
• I misunderstood the question. – Thumbnail Feb 13 '17 at 12:25