Search for question

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