SDE - 1

You are given an array/list ARR consisting of N integers. Your task is to find the length of the longest decreasing subsequence.

A subsequence is a sequence of numbers obtained by deleting zero or more elements from the array/list, keeping the relative positions of elements same as it was in the initial sequence. A decreasing subsequence is a subsequence in which every element is strictly less than the previous number.

Note:

There can be more than one subsequences with the longest length.

For example:-

For the given array [5, 0, 3, 2, 9], the longest decreasing subsequence is of length 3, i.e. [5, 3, 2]

Note:

Try to solve the problem in O(N log N) time complexity.

You are given an array 'a' of size 'n'.

Print the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

For example:

Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- The next greater element for 7 is 12.

- The next greater element for 12 is 20. 

- The next greater element for 1 is 20. 

- There is no greater element for 20 on the right side. So we consider NGE as -1.