3. In class, we studied the longest common subsequence problem. Here we consider

a similar problem, called maximum-sum common subsequence problem, as follows. Let A be

an array of n numbers and B another array of m numbers (they may also be considered as

two sequences of numbers). A maximum-sum common subsequence of A and B is a common

subsequence of the two arrays that has the maximum sum among all common subsequences

of the two arrays (see the example given below). As in the longest common subsequence

problem studied in class, a subsequence of elements of A (or B) is not necessarily consecutive

but follows the same order as in the array. Note that some numbers in the arrays may be

negative.

Design an O(nm) time dynamic programming algorithm to find the maximum-sum common

subsequence of A and B. For simplicity, you only need to return the sum of the elements in

the maximum-sum common subsequence and do not need to report the actual subsequence.

Here is an example. Suppose A = {36, -12, 40, 2, -5, 7,3} and B = {2,7, 36, 5, 2, 4, 3, -5,3}.

Then, the maximum-sum common subsequence is {36, 2,3}. Again, your algorithm only needs

to return their sum, which is 36 +2+3=41.