Longest Decreasing Subsequence Problem Statement

Given an array/list of integers ARR consisting of N integers, your task is to determine the length of the longest decreasing subsequence.

Explanation:

A subsequence is a sequence derived by deleting zero or more elements from the array/list without changing the order of the remaining elements. A decreasing subsequence is one where each subsequent element is strictly less than the previous element.

Input:

T: Integer, number of test cases
N: Integer, size of array/list for each test case
ARR: List of integers, each representing elements of the array/list

Output:

For each test case, output the length of the longest decreasing subsequence.
Separate each test case result with a new line.

Example:

Input:
1
5
[5, 0, 3, 2, 9]
Output:
3

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

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 5000
• 1 ≤ ARR[i] ≤ 10^9
• Time Limit: 1 sec

Note:

There can be more than one subsequence with the longest length.
Attempt to solve the problem in O(N log N) time complexity.