# Maximal Zero Sums Partition

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].

-
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