Question

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

(a) True

(b) False

I have been asked this question in a job interview.

The question is from Longest Increasing Subsequence in portion Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct option is (b) False

To explain: 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}.