Search for question
Question

Exercise 3. DYNAMIC PROGRAMMING. Consider two arrays of nonnegative integers, A = {a¡ :1

n} and B = {b₁ : 1≤ i ≤m}. We call a sequence (ai...ai) from A special if ie+1 ≥ ie + 2 for all

between 1 and k-1. Let a = (aia) and b =

(bj₁) bj) be special sequences from A and B,

respectively. Define the inner product

Design a dynamic programming algorithm that returns the maximal inner product between all possible

pairs of special sequences of equal length, where the length is not specified. For your algorithm, also

report the RAM model time complexity. An example: if A = [3, 5, 2, 2, 7, 4] and B = [3,4,1,6], then the

maximal inner product is 62, obtained by using the special sequences (5, 7) and (4, 6).

Fig: 1