Search for question
Question Exercise 3. DYNAMIC PROGRAMMING. Consider two arrays of nonnegative integers, A = {a¡ :1
Exercise 3. DYNAMIC PROGRAMMING. Consider two arrays of nonnegative integers, A = {a¡ :1n} 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).
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
