Longest Increasing Subsequence: Given an array of numbers A[1 .. n] a subsequence is any subset of these numbers taken in order, of the form A[i1], A[i2], , A[ik] where 1 i1 < i2 < < ik n, and an increasing subsequence is one in which the numbers are getting strictly larger. The longest increasing subsequence is the increasing subsequence of greatest length. For example, the longest increasing subsequence of [5, 2, 8, 6, 3, 6, 9, 7] is 2, 3, 6, 9 of length 4. Design a dynamic programming formulation to solve the longest increasing subsequence problem. a. Provide a recurrence equation for the above problem b. Design an efficient algorithm for the problem and analyze its running time. Hint: Define OPT(i, j) as the length of the longest increasing subsequence of A[j .. n] with all elements greater than A[i].