Data Structure Questions and Answers – Longest Increasing Subsequence

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Longest Increasing Subsequence”.

1. The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it’s length is maximum. This problem can be solved using __________
a) Recursion
b) Dynamic programming
c) Brute force
d) All of the mentioned
View Answer

2. Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
a) {10, 12, 15}
b) {10, 12, 13, 14}
c) {-10, 12, 13, 14}
d) {-10, 9, 10, 13, 14}
View Answer

3. Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a) 5
b) 4
c) 3
d) 6
View Answer

4. For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
a) True
b) False
View Answer

5. The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}
a) 3
b) 4
c) 5
d) 6
View Answer

6. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?
a) O(n)
b) O(n²)
c) O(n!)
d) O(2ⁿ)
View Answer

7. Complete the following dynamic programming implementation of the longest increasing subsequence problem:

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     ___________;  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) tmp_max = LIS[j].
b) LIS[i] = LIS[j].
c) LIS[j] = tmp_max
d) tmp_max = LIS[i].
View Answer

8. What is the time complexity of the ABOVE dynamic programming implementation used to find the length of the longest increasing subsequence?
a) O(1)
b) O(n)
c) O(n²)
d) O(nlogn)
View Answer

9. What is the space complexity of the ABOVE dynamic programming implementation used to find the length of the longest increasing subsequence?
a) O(1)
b) O(n)
c) O(n²)
d) O(nlogn)
View Answer

10. What is the output of the following program?

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	    tmp_max = 0;
	    for(j = 0; j < i; j++)
	    {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		       tmp_max = LIS[j];
	        }
            }
	    LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	  if(LIS[i] > max)
	      max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) 3
b) 4
c) 5
d) 6
View Answer

11. What is the value stored in LIS[5] after the following program is executed?

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	   tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];
	        }
	   }
	   LIS[i] = tmp_max + 1;
       }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	 if(LIS[i] > max)
	     max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) 2
b) 3
c) 4
d) 5
View Answer

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.