Examine if array might be divided into two subsequences merging whom makes Array sorted

Given an integer array A[] of dimension N, the duty is to verify if the array might be divided into two subsequences such that appending considered one of them on the finish of the opposite makes the array sorted.

A sub-sequence is a sequence that may be obtained from the array by deleting some or no parts from it. It could or might not be a steady a part of an array.

Examples:

Enter: arr[] = {1, 4, 5, 2, 3, 4}
Output: Sure
Clarification :
First Sub-Sequence (P) :  {1, 2, 3, 4};
Second Sub-Sequence (Q) : {4, 5};
Merging each Sub-Sequence Provides Sorted Array: 
P+Q = {1, 2, 3, 4} + {4, 5} = {1, 2, 3, 4, 4, 5}

Enter: arr[] = {1, 4, 6, 3, 5}
Output: No

Strategy: The concept behind fixing the issue is:

Make a duplicate of the array and type the copy. Discover two growing subsequences from the array which match the order of the sorted copy. If the mixed parts of each the subsequences type the duplicate of sorted array then such subsequences are doable.

Observe the steps talked about belwo to implement the thought:

• Make a temp[] array which shops all of the ingredient of enter array. 
• Kind the  temp[] array.  
• Iterate twice on unsorted enter array and attempt to discover two sorted sub – sequences, having an order identical as in temp[] array.
  • Merge these two subsequences.
  • If the merged array is a reproduction of the temp[] array then the requirement is glad.
• If such subsequences usually are not doable, return “No” as the reply.

Observe the under illustration for a greater understanding.

Illustration:

Take into account array arr[] = {1, 4, 5, 2, 3, 4};
Thus, temp[] array (sorted of enter array): {1, 2, 3, 4, 4, 5};

First Iteration (discovering first sorted subsequence): 
        => We’ll get parts 1, 2, 3, and 4 which maintains the order as in temp[], 
        => Retailer them in one other array: {1, 2, 3, 4}.  

Second Iteration (discovering second sorted subsequence): 
        => We’ll get 4, 5. 
        => Now add these parts additionally within the new array: {1, 2, 3, 4, 4, 5}.

2 iterations have been accomplished. 
temp[] = new array

So the output can be “Sure”. 

Under is the implementation of this strategy: 

Time Complexity: O(N * log(N))
Auxiliary House: O(N)