Partitioning an array into two arrays using special rule

Question

I've been working on the exercise and stumbled upon a problem.

Given an array of integers, determine whether or not it can be partitioned into two arrays, each of which is in increasing order. For instance 3,1,5,2,4 can, but 4,8,1,5,3 can't.

The problem is here. I couldn't understand why 1st array can but the 2nd one can't.
There is a hint given:
If we successfully partitioned an initial segment of the array, one of the parts must contain the maximum element seen so far. It is obviously in our best interest that the largest element of the other part be as small as possible. So, given the next element, if it's the maximum to this point add it to the "maximum containing part". If not there is no choice but to add it to the other part if possible (e.g: if it is larger than the largest element of this part, but it is not the current maximum). If this procedure fails then no partition is possible, and if it succeeds then we have demonstrated a partition.

The most important part is to understand the logic of this partitioning.
Thank you in advance.

Why it can't? Well, go ahead and try to partition 4,8,1,5,3 into two increasing sequences. That "hint" is basically just the algorithm. — Sneftel
– Sneftel, Commented Feb 11, 2014 at 20:35
Note that any sequence can be partitioned into n increasing sequences, for a sufficiently large n... the only question is, whether it's possible for some sequence and some n. — Sneftel
– Sneftel, Commented Feb 11, 2014 at 20:37
Do you need help seeing how the first can? Or why the second can't? Or why the algorithm is correct? — Beta
– Beta, Commented Feb 11, 2014 at 20:37
@Beta - yes It would be great if I can see how the first one partitions. Thank you — BAT
– BAT, Commented Feb 11, 2014 at 20:39
I think it would be considerably clearer if you also verified moving elements around is actually allowed, as well as the results of applying the aforementioned algorithm to the one that "works". — WhozCraig
– WhozCraig, Commented Feb 11, 2014 at 20:42

Beta · Accepted Answer · 2014-02-11 20:44:14Z

4

Let's use the given algorithm on {3,1,5,2,4}.

First number is 3. Our partition is {3},{}.

Next comes 1. We can't add that to {3}, so we add it to the other: {3},{1}.

Next comes 5. We will add it to {3}, so as to save the {1} for smaller numbers: {3,5},{1}.

Next comes 2. we must add it to {1}: {3,5},{1,2}. (Now we see why it was good not to add 5 to {1}.)

Next comes 4: again, we have no choice: {3,5},{1,2,4}.

answered Feb 11, 2014 at 20:44

Beta

99.5k18 gold badges159 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Partitioning an array into two arrays using special rule

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related