Longest Increasing Subsequence in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

6 practice sets · Page 1 of 1

Data Structure And AlgorithmMediumDynamic ProgrammingLongest Increasing Subsequence

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?

O(n)

O(n^{2})

O(n!)

O(2^{n})

View Answer

Correct Answer: D — O(2^{n})

Explanation:

The time required to find all the subsequences of a given sequence is 2^{n}, where 'n' is the number of elements in the sequence. So, the time complexity is O(2^{n}).

Data Structure And AlgorithmMediumDynamic ProgrammingLongest Increasing Subsequence

The number of increasing subsequences with the longest length for the given sequence are: {10, 9, 8, 7, 6, 5}

View Answer

Correct Answer: D — 6

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.

Data Structure And AlgorithmMediumDynamic ProgrammingLongest Increasing Subsequence

For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.

True

False

View Answer

Correct Answer: B — False

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}.

Data Structure And AlgorithmMediumDynamic ProgrammingLongest Increasing Subsequence

Find the length of the longest increasing subsequence for the given sequence: {-10, 24, -9, 35, -21, 55, -41, 76, 84}

View Answer

Correct Answer: D — 6

Explanation:

The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it's length is 6.

Data Structure And AlgorithmMediumDynamic ProgrammingLongest Increasing Subsequence

Find the longest increasing subsequence for the given sequence: {10, -10, 12, 9, 10, 15, 13, 14}

{10, 12, 15}

{10, 12, 13, 14}

{-10, 12, 13, 14}

{-10, 9, 10, 13, 14}

View Answer

Correct Answer: D — {-10, 9, 10, 13, 14}

Explanation:

The longest increasing subsequence is {-10, 9, 10, 13, 14}.

Data Structure And AlgorithmMediumDynamic ProgrammingLongest Increasing Subsequence

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 __________

Recursion

Dynamic programming

Brute force

Recursion, Dynamic programming, Brute force

View Answer

Correct Answer: D — Recursion, Dynamic programming, Brute force

Explanation:

The longest increasing subsequence problem can be solved using all of the mentioned methods.