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.

This should be in pseudocode.