Longest Increasing Subsequence

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
248 upvotes
Asked in companies
Paytm (One97 Communications Limited)VisaOYO

Problem statement

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example: 
[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer 'N', representing the size of the array.

The second line of input contains 'N' space-separated integers, representing the elements of the array.
Output Format: 
The only output line contains one integer representing the length of the longest increasing subsequence.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Input Constraints 
1 <= N <= 10^5
-10^5 <= element <= 10^5

Time Limit: 1sec
Sample Input :
6
5 4 11 1 16 8
Sample Output 1 :
3
Explanation of Sample Input 1:
Length of longest subsequence is 3 i.e. [5, 11, 16] or [4, 11, 16].
Sample Input 2:
3
1 2 2
Sample Output 2 :
2
Hint

Try to write a recursive algorithm which would try out all the possibilities.

Approaches (4)
Recursive Approach
  • We will write a recursive algorithm that will try all the possibilities.
  • The argument of recursive function will be the current index and what was the previous number used for LIS. Initially, we will be passing the previous number as the minimum number of an integer and starting index as 0.
  • The base case would be when we reach index n,i.e we have exhausted the array elements so return 0 because there is no more element to contribute anything.
  • Inside each function call, we consider two cases: The current element is larger than the previous element included in the LIS. In this case, we can include the current element in the LIS. Thus, we find out the length of the LIS obtained by including it.
  • Further, we also find out the length of LIS possible by not including the current element in the LIS. The value returned by the current function call is, thus, the maximum out of the two lengths.
  • So here is our recurrence relation:
if (arr[curPosition] > prev)
{
	taken = 1 + lisHelper(arr[curPosition], curPosition + 1);
}

int notTaken = lisHelper(prev,curPosition + 1); 
//we can always skip the current element
  • Finally, the answer will be max(taken, notTaken)
Time Complexity

O(2 ^ N), where N is the size of the array.

 

Since every element it will be either used or not so the size of the recursion tree will be 2 ^ N.

Space Complexity

O(N), where N is the size of the array.

 

For stack space in recursion.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Longest Increasing Subsequence
Full screen
Console