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) Recursion, Dynamic programming, Brute force
View Answer

Answer: d
Explanation: The longest increasing subsequence problem can be solved using all of the mentioned methods.

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

Answer: d
Explanation: The longest increasing subsequence is {-10, 9, 10, 13, 14}.

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

Answer: d
Explanation: The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it’s length is 6.
advertisement

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

Answer: b
Explanation: For a given sequence, it is possible that there is more than one subsequence with the longest length.
Consider, the following sequence: {10,11,12,1,2,3}:
There are two longest increasing subsequences: {1,2,3} and {10,11,12}.

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

Answer: d
Explanation: Each array element individually forms a longest increasing subsequence and so, the length of the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length is 6.
Free 30-Day Python Certification Bootcamp is Live. Join Now!

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(n2)
c) O(n!)
d) O(2n)
View Answer

Answer: d
Explanation: The time required to find all the subsequences of a given sequence is 2n, where ‘n’ is the number of elements in the sequence. So, the time complexity is O(2n).

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

Answer: a
Explanation: tmp_max is used to store the maximum length of an increasing subsequence for any ‘j’ such that: arr[j] < arr[i] and 0 < j < i.
So, tmp_max = LIS[j] completes the code.
advertisement

8. What is the time complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#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) O(1)
b) O(n)
c) O(n2)
d) O(nlogn)
View Answer

Answer: c
Explanation: The time complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n2).

9. What is the space complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#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) O(1)
b) O(n)
c) O(n2)
d) O(nlogn)
View Answer

Answer: b
Explanation: The above dynamic programming implementation uses space equal to the length of the sequence. So, the space complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n).

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

Answer: d
Explanation: The program prints the length of the longest increasing subsequence, which is 6.

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

Answer: c
Explanation: The value stored in LIS[5] after the program is executed is 4.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.