Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should belong to exactly one subsequence. Maximize the number of subsequences. It is not required that elements in subsequences are consecutive.

It seems the problem is NP-hard (or "Can the sequence be partitioned into $k$ subsequences which all have zero sums?" is NP-complete), but can't prove it.

Example: the maximal number of subsequences for the sequence [2, 0, 1, -1, -1, -1] is 3: [0], [2, -1, -1] and [1, -1].

share|improve this question
    
this is phrased like HW (imperative tone); might get closed soon. –  Suvrit Mar 23 '13 at 22:51
    
It is not a HW or similar. Maybe my wording is not good. –  silentbob Mar 23 '13 at 23:09
    
Answered on math.stackexchange.com/questions/339148/… How to hide the question? –  silentbob Mar 24 '13 at 8:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.