Number of Longest Increasing Subsequence

Moderate
0/80
profile
Contributed by
45 upvotes
Asked in companies
AmazonSamsungTata1mg

Problem statement

Given an integer array ‘arr’ of length ‘n’, return the number of longest increasing subsequences in it.


The longest increasing subsequence(LIS) is the longest subsequence of the given sequence such that all subsequent elements are in strictly increasing order.


Example: 
Input: ‘n’ = 5, ‘arr’ = [50, 3, 90, 60, 80].

Output: 2

Explanation: 
In this array, the longest increasing subsequences are [50, 60, 80] and [3, 60, 80]. 

There are other increasing subsequences as well, but we need the number of the longest ones. Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of each test case contains a single integer ‘n’ denoting the length of the array ‘arr’.

The following line contains ‘n’ space-separated integers representing elements in ‘arr’.
Output Format : 
For each test case, return an integer representing the number of longest increasing subsequences.
Note : 
You are not required to print anything. It has already been taken care of. Just implement the function.
Sample Input 1 :
4
3 7 4 6
Sample Output 1 :
1
Explanation For Sample Input 1 :
The length of LIS is 3, and there is only one such LIS, which is [3, 4, 6].
Sample Input 2 :
4
5 7 2 3
Sample Output 2 :
2
Explanation For Sample Input 2 :
The length of LIS is 2, and there are two such LIS, which are [5, 7] and [2, 3].
Expected Time Complexity:
The expected time complexity is O(n^2).
Constraints :
1 ≤ ‘n’ ≤ 5000
1 ≤ ‘arr’[i] ≤ 10 ^ 6

Time limit: 1 sec
Hint

Generate all possible subsequences present in the array and count the increasing subsequences of maximum length.

Approaches (3)
Recursion

The simplest approach is to generate all possible subsequences present in the given array ‘arr’ and count the increasing subsequences of maximum length. Print the count after checking all subsequences.

 

For every element in the array, there are two choices, either to include it in the subsequence or not include it. Apply this for every element in the array starting from index 0 until we reach the last index. After we reach the last index, we check if this is an increasing subsequence and if so, then we increment the count of the size of this subsequence by 1.

 

At last, we simply traverse the count array and find the frequency of the max count.

 

The steps are as follows :

  1. Create a recursive function and pass three arguments :
    • array ‘arr’
    • index ‘i’
    • subarray ‘subArr’ (This will store the current subsequence)
  2. When we reach the end of array ‘arr’ i.e. ‘i’ is equal to ‘n’, we check if this is an increasing subsequence so we increment its count by one.
  3. Create an array ‘count’, where at each index ‘i’ we store the number of LIS of length ‘i’.
  4. If we have not reached the end of ‘arr’, then we make two recursive calls, one without including the current element and the other including the current element.
  5. At last, traverse the ‘count’ array and find the frequency of max count.
Time Complexity

O( n * (2 ^ n ) ), where n is the length of the array ‘arr’.

 

We generate ~( 2 ^ n) subsequences. For each subsequence generated we take ~O( n ) time to verify if it is an increasing subsequence. 

 

Hence the time complexity is O( n * (2 ^ n ) ).

Space Complexity

O( n ), where n is the length of the array ‘arr’.

 

‘count’ array requires O ( n ) space. Also, we use the array ‘subArr’ in which at max ~( n ) elements can be there.

 

Hence the space complexity is O( n ).

Code Solution
(100% EXP penalty)
Number of Longest Increasing Subsequence
Full screen
Console