In class we showed how to calculate the longest increasing subsequence. This requirement turned out too strict and we are interested to finding the longest close-to-increasing subsequence. We say that a sequence of numbers Z is close-to-increasing if the size of any decreasing substring is at most 2. So given two consecutive elements in the sequence Z and Zi+ı it must either be that • Z; Zi+1 it must be that Zi+1 A=11 10 18 17 25 33 30 34 27 29
B=8 99 33 34 40 11 13 20 23 22 As we can see A2 = 10 11 = A, but A3 = 12 > 10 = Ay so the constraint is satisfied. Same is true in other places where monotonicity fails at A7, A11. 414. Similar for sequence B. The following are examples of sequences that are not close-to-increasing: C = 10 11 12 18 30 27 22 33 D = 17 16 1 11 13 12 15 19 30 25 We have C6 = 30 > 27 = C7 and Co = 27 > 22 = Cg so the constraint is violated. Similarly D > D, > D3 so the sequence D is not close-to-increasing. For example if X = D the longest close-to-increasing subsequence is Z = 17, 1, 11, 13, 12, 15, 19.30,25,33 for a size of 11. You may assume all numbers in X are unique. a. (35 points) Give a dynamic programming algorithm using the following optimal subproblem structure LCIS+(1,7): is the longest closed to increasing subsequence that ends and X;X;, i.e., its last element is X, and its second to last element is X. Give a recursive formula, prove its correctness and write a bottom-up implementation. b. (Bonus 10 points) Give a dynamic programming algorithm using the following optimal subproblem structure LCIS+() is the longest closed to increasing subsequence that ends and X, and the auxiliary optimal subproblem structure LCIST.inc() is the longest closed to increasing subsequence that ends at X; in an increasing fashion (the second to last element is smaller than X:). Give a recursive formula for both optimal subproblem structures, prove their correctness and write a bottom-up implementation.