### saifhaider0z's blog

By saifhaider0z, history, 4 months ago, ,

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

• +6

 » 4 months ago, # | ← Rev. 2 →   0 oops!
•  » » 4 months ago, # ^ |   +4 3 2 1NANI??
•  » » » 4 months ago, # ^ |   0 Answer Should be "NO"
 » 4 months ago, # | ← Rev. 2 →   +11 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.
•  » » 4 months ago, # ^ |   +3 I thought of that thing but was unable to prove
•  » » » 4 months ago, # ^ |   0 I edited the comment, new solution seems right to me.
 » 4 months ago, # |   0 Auto comment: topic has been updated by saifhaider0z (previous revision, new revision, compare).
 » 4 months ago, # |   +11 I think the problem 1144G - Two Merged Sequences is almost the same as yours.
 » 4 months ago, # |   0 Check this comment for a really good solution (but for a one increasing and a one decreasing subsequence):Two merged subsequences greedy ideaYou 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).
 » 4 months ago, # |   +12 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.