Longest Subsequence with distinction between max and min at most Ok

Given an array arr[] of dimension N and a non-negative integer Ok, the duty is to seek out the size of the longest subsequence such that the distinction between the utmost and the minimal of the subsequence is at most Ok.

Examples:

Enter: arr[] = {1, 3, 5, 4, 2}, N = 5, Ok = 3
Output: 4
Rationalization: If we think about, the sequence {1, 3, 4, 2}. The subsequence most component is 4 and minimal component is 1 and their absolute distinction is 3. So most size amongst all subsequence is 4.

Enter: arr[] = {5, 5, 5, 5, 5}, N = 5, Ok = 1
Output: 5

Naive Strategy: The only manner is to generate all doable subsequence and discover the longest amongst them having the distinction between the utmost and the minimal at most Ok.

Time Complexity: O(N * 2^N)
Auxiliary House: O(N)

Environment friendly Strategy: The issue might be solved effectively utilizing sorting based mostly on the next concept:

If we type the array we are able to get the weather in sorted order. Now the duty reduces to discovering the longest window such that the distinction between the final and first component of the window is at most Ok. This may be solved utilizing two pointer approach.

Observe the steps talked about beneath to implement the thought:

•  Kind the array arr[] in ascending order.
•  Initialize, i = 0,  j = 0 to implement the 2 pointer method and MaxSize = 0 to retailer the size of the longest subsequence.
• Run a loop until j < N:
  • If, (arr[j] – arr[i]) ≤ Ok [Because the array is sorted so arr[j] is most and arr[i] is minimal], replace, the MaxSize  to have the utmost size and increment j by 1.
  • Else increment i by 1.
• Return MaxSize because the required most size.

Under is the implementation of the above method.

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