Last Updated: 31 Dec, 2020
Longest Increasing Subsequence
Moderate
Asked in companies
'N' students are standing in a row. You are given the height of every student standing in the row. Your task is to find the longest strictly increasing subsequence of heights from the row such that the relative order of the students does not change.
A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains an integer ‘N’ , the number of students in the row.
The second line of each test case contains ‘N’ space separated integers representing the height of every student in the row.
Output format:
For each test case, return the length of longest strictly increasing subsequence of heights.
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 <= 200
1 <= heights[i] <=10^9
Time Limit: 1 sec
Approaches
The idea is to find strictly increasing subsequences for all the elements of the array once including the elements in the sequence and once excluding it. In order to do this, we use a recursive function, 'LIS_HELPER' which returns the length of LIS possible from the current element (maximum of the lengths of subsequences once including the current element and once excluding it).
Algorithm:
- Recursive Function: 'LIS_HELPER'(heights, 'PRE', 'CURR'), where ‘heights’ is the list of heights, ‘'PRE'’ is the previous height considered in the current subsequence and 'CURR’ is the index of the current element of the height array.
- Base condition => if 'CURR' = ‘N’ , return 0
- There will be two cases :
- If the current height is larger than the previous height included in the LIS : In this case we once include the current height in the LIS and once exclude the current height from the LIS and return the maximum of lengths obtained from both the cases.
- If the current height is smaller or equal to the previous height included in the LIS : we cannot include the current height in the LIS and thus return the length of the LIS that we obtain by excluding the current height.
LIS => Longest Increasing Subsequence.
Here, LIS(4) corresponds to LIS found up to index 4. LIS(4) will be calculated with the help of LIS(3), LIS(2), LIS(1).
Now, LIS(3) is calculated using the values of LIS(2) and LIS(1).
As you can see in the figure above this leads to recomputation of the same data again and again.
The idea is the same as the previous approach, but in the previous approach, many recursive calls were made again and again with the same parameters. This can be eliminated by storing the value obtained from a particular call in a 2d array, called the 'MEMO' array. 'MEMO'[i][j] stores the length of the LIS possible using 'HEIGHTS'[i] as the previous height(included / not included in LIS), and 'HEIGHTS'[j] as the current height(included / not included in LIS).
Algorithm:
- An array, 'MEMO', of size ‘N*N’ is taken.
- Recursive Function: 'LIS_HELPER'( 'HEIGHTS', 'PREV', 'CURR'), where ‘HEIGHT’ is the list of 'HEIGHTS', ‘'PREV'’ is the previous index considered in the current subsequence and 'CURR' is the index of the current element of the height array. The initial call of this function will have 'PREV' = -1 and 'CURR' = 0 as arguments.
- Base condition => 'CURR' = ‘N’ , return 0
- If the value at 'MEMO'['PREV'+1]['CURR'] is not -1, use this value, that is, return it.
- There will be two cases :
- If the current height is larger than the previous height included in the LIS: In this case, we once include the current height in the LIS and once exclude the current height from the LIS and return the maximum of lengths obtained from both the cases.
- If the current height is smaller or equal to the previous height included in the LIS: we exclude it from the LIS and return the length of the LIS obtained.
- Update the value returned by above recursive call in 'MEMO'['PREV'+1]['CURR']
This approach relies on the fact that the LIS possible upto ith index is independent of the elements coming after the ith index. Thus, for every index we will store the length of LIS possible upto that index in an array, say 'DP' array. For every index there will be two cases :
- Iterate over the indices for all ‘j’ such that 0 <= j <= i-1, and if the value at 'HEIGHTS'[j] is less than the value at 'HEIGHTS'[i], include the current element in the LIS and check whether its length is greater than the longest length found so far.
- Find the length of LIS formed before the current index.
- Return the maximum of the two cases.
Algorithm:
- Take a 'DP' array of size ‘N’ and initialize all its values with 0.
- 'DP'[0] = 1
- For every index ‘i’ of the 'HEIGHTS' array
- Iterate over the indices for all ‘j’ such that 0 <= j <= i-1, and if the value at 'HEIGHTS'[j] is less than the value at 'HEIGHTS'[i], 'DP'[i] = max('DP'[i], 1+'DP'[j]).
- At the end of the above iteration, 'DP'[i] = max('DP'[i], 'MAX_VALUE'). 'MAX_VALUE' is the length of LIS found before the current index.
- Update the value of 'MAX_VALUE' = max('MAX_VALUE', 'DP'[i]).
- Return the value of 'DP'[N-1] that is the length of LIS found upto the last value of the input.