Question

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.

Answer 1

The recurrence relation for LMS(i) is LMS(i) = max(LMS(j) + 1) for all j < i and A[j] < A[i]. This can be converted into a dynamic program by initializing an array LMS and using a loop to calculate LMS[i] for each index i.

Step-by-step explanation:

The length of the longest monotonically increasing subsequence can be found using dynamic programming. We can define the recurrence relation as follows: LMS(i) = max(LMS(j) + 1) for all j < i and A[j] < A[i]. This means that LMS(i) is the maximum length of the monotonically increasing subsequence ending at index i, which is obtained by adding 1 to the length of the longest monotonically increasing subsequence ending at any index j before i, where A[j] < A[i].

To convert this into a dynamic program, we can initialize an array LMS of size n, where each LMS[i] represents the length of the longest monotonically increasing subsequence ending at index i. We can start by setting LMS[1] = 1, as the subsequence with only the first element will have a length of 1 by default. Then, for every index i from 2 to n, we can calculate LMS[i] using the recurrence relation mentioned earlier. Finally, the maximum value in the LMS array will represent the length of the longest monotonically increasing subsequence of the entire array A.