Last Updated: 3 Sep, 2021

Decreasing Subsequences

Moderate

Asked in companies

Solve now

Problem statement

Ninja is fond of sequences. He has a set of numbers and wants to make minimum decreasing subsequences such that all numbers are part of exactly one subsequence. Can you help Ninja with this challenge?

You are given an array ‘ARR’ having ‘N’ elements.Your task is to divide all ‘N’ elements of the array into a minimum number of strictly decreasing subsequences. Each number can be in one subsequence only. Find the minimum number of such strictly decreasing subsequences.

For Example

If 'ARR' is [4,2,1,3] ,it can be splitted into two subsequences as [4,2,1] , [3] or [4,3],[2,1].

Input Format:

The first line of the input contains an integer, 'T’ , denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of elements in ‘ARR’.

The next line of each test case has ‘N’ integers corresponding to the elements of 'ARR’.

Output Format:

For each test case, print a single integer corresponding to the minimum number of subsequences.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 2000
1 <= 'ARR'[i]   <= 10^6

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will prepare an array ‘USED ’ as USED[i] will state that whether any element can be inserted after ARR[i] or not. We will also maintain ‘ANS’ to store the number of subsequences. For each element, we will try also values left to that element and greedily pick the element whose value is just less than ARR[i]. If no such element is found, we will create a new subsequence and increase the value of ‘ANS’ by 1.

Algorithm:

Declare an array ‘USED’ to store whether we can add any element next to ARR[i] or not.
Declare a variable ‘ANS’ to store the number of subsequences.
For each index ‘i’ in range 0 to ‘N-1’,do the following:
- Set USED[i] as 1.
For each index ‘i’ in range 0 to ‘N-1’, do the following:
- Set ‘INDEX’ as -1.
- For each index ‘j’ in range 0 to ‘i-1’,do the following:
  - If ‘USED[j]’ == 1 and ‘ARR[j]’ > ‘ARR[i]’:
    - If ‘INDEX’ == -1
      - Set ‘INDEX’ as ‘j’.
    - Else, if difference of ‘ARR[i]’ and ‘ARR[j]’ is less than ‘ARR[i]’ and ‘ARR[INDEX]’:
      - Set ‘INDEX’ as ‘j’.
- If ‘INDEX’ == -1 ,no suitable element found.We will put ‘ARR[i]’ into a new subsequence:
  - Set ‘ANS’ as ‘ANS +1’.
- Else
  - Set ‘USED[INDEX]’ as 0.
Return ‘ANS’.

Solve now

02 Approach

In this approach, we will prepare an array ‘SUBSEQUENCES’ to store the last element of each subsequence, and for each element, we will greedily pick the best subsequence using binary search over the ‘SUBSEQUENCES’ array. At last, we will return the size of the ‘SUBSEQUENCES’ array.

Algorithm:

Declare a function binarySearch(VAL, ARR) that will return the index of the element in ‘ARR’ whose value is just greater than ‘VAL’.
- Set ‘ANS’ as the length of ‘ARR’.
- Set ‘L’ as 0.
- Set ‘R’ as the length of ‘ARR -1’.
- While ‘L’ is than or equal to ‘R’, do the following:
  - Set ‘MID’ as ('L'+'R') / 2.
  - If ‘ARR[MID]’ is greater than ‘VAL' :
    - Set ‘ANS’ as ‘MID’
    - Set ‘R’ as ‘MID-1’.
  - Else:
    - Set ‘L’ as ‘MID+1’.
- Return ‘ANS’
Declare a dynamic array ‘SUBSEQUENCES’.
For each index ‘i’ in range 0 to ‘N-1’,do the following:
- Set ‘INDEX’ as binarySearch(ARR,ARR[i]).
- If ‘INDEX’ is equal to the size of ‘SUBSEQUENCES’, it denotes that ‘ARR[i]’ does not fit in any subsequence, So we will make a new subsequence.
  - Insert ‘ARR[i]’ into ‘SUBSEQUENCES’.
- Else:
  - We will add this element to ‘SUBSEQUENCES[INDEX]’ and set the last element of ‘SUBSEQUENCES[INDEX]’ as ‘ARR[i]’.
Return size of ‘SEQUENCES’ array.

Solve now