16
Specification
This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few increasing subsequences as possible.
More formally, if the input array is A
, then the output is an array of arrays B
such that:
- Each arrays in
B
form a partition ofA
into disjoint (not necessarily contiguous) subsequences. Inductively, this means that eitherB
is the singleton array containingA
, or the first element ofB
is a subsequence ofA
and the rest form a partition ofA
with that subsequence removed. - Every array in
B
is (not necessarily strictly) increasing. - The number of arrays in
B
is minimal.
Both the input and output can be taken in the native array format of your language. Note that there may be several correct outputs.
Example
Consider the input array A = [1,2,1,2,5,4,7,1]
.
One possible output is B = [[1],[1,2,4,7],[1,2,5]]
.
The partition condition is evident from this diagram:
A 1 2 1 2 5 4 7 1
B[0] 1
B[1] 1 2 4 7
B[2] 1 2 5
Also, each array in B
is increasing.
Finally, A
can't be split into two increasing subsequences, so the length of B
is also minimal.
Thus it's a valid output.
Rules and scoring
You can write a function or a full program. The lowest byte count wins, and standard loopholes are disallowed. There is no time bound, but you should evauate your solution on all test cases before submitting it.
Test cases
Only one possible output is shown, but there may be several valid options. In particular, the order of the arrays in the result doesn't matter (but each individual array should be in increasing order).
[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
3The rules seem to allow solutions like
[0,5,2,0] -> [[0,5],[0,2]]
(i.e., recycling the first zero instead of using each of them once). Is that intentional? – feersum – 2015-12-07T05:28:34.147@feersum That wasn't intentional, good catch. I've rewritten the conditions for
B
, hopefully they're clearer now. – Zgarb – 2015-12-07T15:39:15.967