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?

1. 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? nother example if A=[10229332150416080] then LMS=6, there are 2 solutions here [10 223350 0 80] or [10 2333416080]. You don't have to output the sequence juts its length. \} 1. 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? nother example if A=[10229332150416080] then LMS=6, there are 2 solutions here [10 223350 0 80] or [10 2333416080]. You don't have to output the sequence juts its length. \}