Given an array A[1..n] representing a sequence of n integers, a subsequence is a subset of elements of A, in the same order as they appear in A. A subsequence is monotonic if it is a sequence of strictly increasing numbers. Define LMS(i) to be the length of a longest monotonically increasing subsequence of A[1..i] that must have A[i] as its last element. Write a recurrence for LMS(i) and convert into a dynamic program that calculates LMS(i) for i=1..n. What is the running time of your algorithm? {For example if A = [8 9 12 10 11] then LMS = 4 which is [8, 9, 10, 11] Another example if A = [10 22 9 33 21 50 41 60 80] then LMS = 6, there are 2 solutions here [10 22 33 50 60 80] or [10 23 33 41 60 80]. You don’t have to output the sequence juts its length. }