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

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 Ai] as its last element. Write a recurrence for LMS(i) and convert into a dynamic program that calculates LMS() for 1:1..n