4. Given an array A[1...n] of n distinct numbers (i.e., no two numbers of A are

equal), design an O(n²) time dynamic programming algorithm to find a longest monotonically

increasing subsequence of A (see the formal definition below). Your algorithm needs to report

not only the length but also the actual longest subsequence (i.e., report all elements in the

subsequence).

Here is a formal definition of a longest monotonically increasing subsequence of A (refer to the

example given below). First of all, a subsequence of A is a subset of numbers of A such that

if a number a appears in front of another number b in the subsequence, then a is also in front

of b in A (i.e., the subsequence follows the same order as in A). Next, a subsequence of A is

monotonically increasing if for any two numbers a and b such that a appears in front of b in

the subsequence, a is smaller than b. Finally, a longest monotonically increasing subsequence

of A refers to a monotonically increasing subsequence of A that is the longest (i.e., has the

maximum number of elements) among all monotonically increasing subsequences of A.

For example, if A = {20, 5, 14, 8, 10, 3, 12, 7, 16}, then a longest monotonically increasing

subsequence is 5, 8, 10, 12, 16. Note that the answer may not be unique, in which case you

may report any one of such longest subsequences.