Question 8
Consider the following greedy approach to find the Longest Increasing Subsequence (LIS):
Select the first element of the list. Then repeatedly select the next element that is strictly larger than the last selected element.
On which of the following inputs does this greedy algorithm give an incorrect answer?
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
[15, 1, 2, 3, 4, 5, 6, 7, 8, 16]
[2, 9, 3, 6, 5, 1, 7, 8, 4, 10]