Consider the following problem. You are given an unordered list of integers x1,
ID: 3799479 • Letter: C
Question
Consider the following problem. You are given an unordered list of integers x1, x2, x3, ….. xn. You wish to find the Longest Increasing Subsequence (LIS) inside the given list. For example, if you have the list:
L = 4, 3, 7, 5, 1, 9, 6, 2, 8
Then a “longest increasing subsequence” is: 3, 5, 6, 8, since this sequence is increasing in value, and it is a sub-sequence of the original list. Note that 4, 5, 6, 8 is also a solution.
Consider the following greedy algorithm for the LIS problem:
Take the first element of the List as the first element of the solution. Then scan the list from left-to-right, and add the next List element to the solution if-and-only if it is larger than the last element in the solution list.
What solution does this greedy algorithm produce for the list above?
Enter your answer here as a list of number, separated by commas, with no blank spaces.
Explanation / Answer
Given Constrain:
Take the first element of the List as the first element of the solution.
Then scan the list from left-to-right, and add the next List element to the
solution if-and-only if it is larger than the last element in the solution list.
List => L = 4, 3, 7, 5, 1, 9, 6, 2, 8
So, produced the list for above:
4 7 9