Min operations to empty an array by erasing any rising subsequence

Given array A[] of dimension N, the duty is to search out the variety of operations to empty the array by performing the next operation a number of occasions. In a single operation select any strictly rising subsequence and delete it from A[].

Examples:

Enter: A[] = {2, 1, 4, 5, 3}
Output: 2
Clarification: Following operations are carried out to empty the array:

• Selecting rising subsequence {2, 4, 5} and eradicating it from A[], A[] turns into {1, 3}
• Selecting rising subsequence {1, 3} and eradicating it from A[], A[] turns into empty.

Enter: A[] = {0, 0, 0, 0}
Output:  4

Strategy: The thought is to make use of a Precedence Queue knowledge construction to unravel this downside.

Iterate over the array and maintain inserting new component to precedence queue, if given component is inserted at non-starting place than delete component simply earlier to that place.

Beneath are the steps for the above method:

• Create precedence queue pq[] utilizing a multiset container to retailer the array parts in sorted order.
• Iterate from 0 to N – 1.
  • For every iteration, insert the present component in pq[].
  • For every iteration, search the present component in pq[].
• If the present component is on the preliminary place within the precedence queue, transfer to the following iteration, else erase the earlier component within the precedence queue.
• Return the scale of pq[] which would be the reply. 

Beneath is the code for the above method:

Time Complexity: O(NlogN)
Auxiliary House: O(N)

Associated Articles :