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.

Answer 1

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