Longest Increasing Subsequence

Moderate
0/80
profile
Contributed by
16 upvotes
Asked in companies
GrabAmazonSamsung

Problem statement

'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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
6
5 8 3 7 9 1

Sample Output 1:

3

Explanation of Sample Input 1:

The longest increasing subsequence is 5 7 9, with length 3.

Sample Input 2:

1
16
1 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Sample Output 2:

6

Explanation of sample output 2:

The longest increasing subsequences are {1 2 6 9 13 15}, {1 4 6 9 13 15},  with length 6.
Hint

Find all possible strictly increasing subsequences and return the length of the longest. 

Approaches (3)
Brute force approach

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.
Time Complexity

O(2^N) where ‘N’ is the number of students in the row.

 

Every student has two options in the worst case, whether to be a part of the current subsequence or not. This leads to a time complexity of O(2*2*2……...N terms). Thus, the total time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the number of students in the row. 

 

We are using recursion. So O(N) space will be taken by the recursion stack. Thus the final space complexity is O(N).

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