saifhaider0z's blog

Spit Array into two such that both part form Strictly Increasing Subsequence
By saifhaider0z, history, 6 years ago, In English

I wanna ask is there any why by which we can check that a given array can be split int two subsequence such that both are Strictly increasing. If not Possible Output is "NO" else "YES".

Better approach than O(2^n).

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

oops!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Don't read the previous version of this comment.

Solution: let's notice that if there are i, j such that i < j and a[i] >= a[j], then i and j belong to different SIS. Then, if there are such i, j, k such that i < j < k and a[i] >= a[j] >= a[k], all of them belong to different SIS, so there is no answer in this case. There is always an answer if there are no such i, j, k, because in this case: for every i, j such that i < j and a[i] >= a[j], every k from j + 1 to n will be such that a[k] > a[i] and a[k] > a[j], ==> we can add k to the SIS of i or j. So all you need to do is check if there is non-increasing subsequence of length more than 2. In this and only in this case there is no answer.

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think the problem 1144G - Two Merged Sequences is almost the same as yours.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this comment for a really good solution (but for a one increasing and a one decreasing subsequence):

Two merged subsequences greedy idea

You can adapt it easily to your situation with the following main modification:

If an element can be put in both arrays, but it in the array that has a larger last element (To give a chance for smaller elements to be put in the other array later).

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

We can do DP using the fact that the previous element must belong to increasing or decreasing subsequence. If we know to which it belongs, then we know whether we should minimize or maximize the last element of the other subsequence.

Go from left to right and store two variables: $$$smallest$$$ and $$$biggest$$$. When you are at position $$$i$$$, the variable $$$smallest$$$ is the smallest possible last element of the increasing subsequence, assuming that position $$$i-1$$$ was taken to the decreasing subsequence. And the same opposite thing for $$$biggest$$$ and assumption that $$$i-1$$$ is in the increasing subsequence.

→ Reply