Longest Increasing Subsequence
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.

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

Question

Longest Increasing Subsequence

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.

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

Accepted Answer

As there are many subproblems in the recursive solution which are solved again and again. So this problem has Overlapping Substructure property and re-computation of same subproblems can be avoided by either using Memoization or Tabulation.

The simulation of approach will make things clear:

Input : arr[] = {3, 10, 2, 11}
LIS[] = {1, 1, 1, 1} (initially)

Iteration-wise simulation :

arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2}
arr[3] < arr[1] {No change}
arr[3] < arr[2] {No change}
arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2}
arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3}
arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3}

Complexity Analysis:

Time Complexity: O(n2).
As nested loop is used.
Auxiliary Space: O(n).
Use of any array to store LIS values at each index

Accepted Answer

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)

Space Complexity: O(n)Explanation:

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

For stack space in recursion.

Time Complexity: O(2^n)Explanation:

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.

Accepted Answer

Memoization

We will write a recursive algorithm that will try all the possibilities and then memorize them.
The argument of recursive function will be the current index and what was the previous index of the array whose element is used for LIS. Initially, we will be passing the previous index as -1 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.
Before calling the recursive function check in the dp array if we have calculated this state before if yes return it’s value otherwise calculate.
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 (curPosition==0 || arr[curPosition] > arr[prevPosition])
    {
    	taken = 1 + longestIncreasingSubsequenceHelper(      
  			curPosition, curPosition + 1);
    }
        
    //we can always skip the current element
    int notTaken = 	longestIncreasingSubsequenceHelper(prevPosition, curPosition + 1); 
    
     //Now memoize it at 
     dp[prevPosition+1][curPosition] = max(taken, notTaken)

Now return this value.

Space Complexity: O(n^2)Explanation:

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

As the 2-Dimensional array is used of size N * N.

Time Complexity: O(n^2)Explanation:

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

Because now the size of the recursion tree will be reduced to O(N ^ 2) because of storing the unique state in dp array which will reduce the redundancy.

Accepted Answer

Iterative DP

dp[i] stores the max length of the LIS ending at position ‘i’.
In order to find out dp[i + 1], we need to try to append the current element in every possible increasing subsequence up to the i’th index, such that the new sequence formed by adding the current element is also an increasing subsequence.
Thus, we can easily determine dp[i] using:
- dp[i + 1] = max(dp[j]) + 1, ∀ 0 ≤ j <= i and arr[i + 1] > arr[j]
3. In the end, the maximum out of all the dp[i]'s to determine the final result.

Space Complexity: O(n)Explanation:

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

As an array is used of size N.

Time Complexity: O(n^2)Explanation:

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

Because we are running two nested loops of size N.

Accepted Answer

Binary Search + DP

In this approach, we scan the array from left to right. We also make use of a dp array. This dp array is meant to store the increasing subsequence formed by including the currently encountered element.
That is dp[i] represents i + 1’th length LIS ending at a minimum element dp[i].
While traversing the array, we keep on filling the dp array with the elements encountered so far. For the element corresponding to the jth index, we determine its correct position in the dp array by making use of Binary Search(which can be used since the dp array is storing increasing subsequence) and also insert it at the correct position.
An important point to be noted is that for Binary Search, we consider only that portion of the dp array in which we have made the updates by inserting some elements at their correct positions(which remains always sorted). Thus, only the elements up to the i’th index in the dp array can determine the position of the current element in it.
Since the element enters its correct position in ascending order in the dp array, the subsequence formed so far in it is surely an increasing subsequence. Whenever this position index i becomes equal to the length of the LIS formed so far let’s say L, it means, we need to update the L as L = L + 1.
In the end, L will be the answer

Space Complexity: O(n)Explanation:

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

As an array is used of size N.

Time Complexity: O(nlogn)Explanation:

O(N * logN), Where N is the size of the array.

For every index, we are performing a binary search that takes O(logN).

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:

Input format:

Output Format:

Note:

Input Constraints

Top Infosys SDE interview questions & answers

Popular interview questions of SDE

Top HR questions asked in Infosys SDE