Last Updated: 25 Apr, 2021
Maximise Dot Product
Hard
Asked in companies
You are given two arrays of positive integers ‘ARR1’ and ‘ARR2’ of length ‘N’ and ‘M’ respectively, where ‘N’ >= ‘M’.
Dot product of 2 arrays ‘ARR1’ and ‘ARR2’ of size ‘N’ is defined as ‘ARR1[i]*ARR2[i]’ for ‘1 <= i <= N’.
You are allowed to insert a certain number of 0s in ‘ARR2’ to make its size equal to ‘N’, but you cannot change the initial ordering of its elements. What is the maximum dot product of ‘ARR1’ and ‘ARR2’ you can achieve by doing this operation optimally?
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first line of each test case contains two positive integers, ‘N’ and ‘M’ denoting the size of the array ‘ARR1’ and ‘ARR2’ respectively.
The second line of each test case contains ‘N’ space-separated positive integers denoting the elements of ‘ARR1’.
The third line of each test case contains ‘M’ space-separated positive integers denoting the elements of ‘ARR2’.
Output Format :
For each test case, print a single positive integer, the maximum value of the dot product between ‘ARR1’ and ‘ARR2’.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’, ‘M’ <= 1000
1 <= ‘ARR1[i]’, ‘ARR2[i]’ <= 1000
Where ‘T’ is the number of test cases, ‘N’, ‘M’ is the size of the arrays, and ARR1[i], ARR2[i] is the ith element of each of the arrays respectively.
Time Limit: 1 sec
Approaches
- Suppose we are looking at index IDX in ARR2. The elements from index 0 to IDX have been properly placed and 0’s have been inserted at some of these positions.
- For the current index IDX, we have 2 options. Either we insert a 0 at this index and let the next element in ARR2 go to a farther position or we use the next element of ARR2 at this index.
- Therefore, for every index of ARR2, we can check what the final answer is if we use a 0 here, or if we use one of the upcoming values of ARR2 here.
- Use a function RECUR which takes in parameters:
- IDX, the current index where we need to choose if we want a 0 or not.
- REMAIN, how many remaining numbers do we have from ARR2? In the end, when IDX = N-1, REMAIN should become 0.
- Run this function RECUR with IDX = 0, and REMAIN = M. After every array construction, find the dot product, and store the maximum found answer in a global variable ANS.
- In the end, return the value of ANS.
- We are repeatedly solving the same subproblems in the previous approach. Therefore we have overlapping subproblems here.
- We need to use memoization to avoid computing the same subproblems again and again.
- This time along with a modified version of the recursive function, let’s have a global array MEMO, such that MEMO[i][j] stores the maximum dot product of ARR1, of size i, with ARR2, till index j. Our final answer therefore will be MEMO[N][M-1].
- The recursive function RECUR now takes in parameters:
- int ARR1[], the initial array ARR1.
- int ARR2[], the initial array ARR2.
- int IDX, which stores which index of ARR2 are we trying to pair with some index in ARR1.
- int A_RIGHT, which stores up to what index we can use ARR1. In this case, we can use ARR1 from 0 to A_RIGHT - 1.
- Call RECUR(ARR1, ARR2, N, M-1). As initially we can use array A from index 0 to N-1 and can use ARR2 from index 0 to M-1.
- At any step, ARR2[IDX] can be a dot product with any index of A in the range [IDX, A_RIGHT - 1]. We cannot pair ARR2[IDX] with any index of ARR1 less than IDX, as there are IDX-1 elements remaining in ARR2 which will later need to be paired.
- Therefore for a certain A_RIGHT and IDX, run a loop i in RECUR from [IDX, A_RIGHT-1] and assign MEMO[A_RIGHT][IDX] = max(MEMO[A_RIGHT][IDX], ARR1[i]*ARR2[IDX] + RECUR(ARR1, ARR2, i, IDX-1)).
- Run this recursive function until IDX is greater than equal to 0.
- In the end, return the value of MEMO[N][M-1].
- In the last approach we used a recursive top-down approach to find the answer, this time we will use an iterative bottom-up approach.
- Create a 2-dimensional dp array, such that dp[i][j] will give us the maximum dot product of ARR1 from index 0 to i with ARR2 from index 0 to j.
- For every pair of elements ARR1[i] and ARR2[j] we have 2 options:
- One, we include ARR1[i] i.e we pair ARR1[i] and ARR2[j] for the dot product.
- Two, we do not pair ARR2[j] with ARR1[i] and instead pair ARR1[i] with 0 and ARR2[j] with some previous element in ARR1.
- The recurrence relation then becomes: dp[i][j] is max of
- dp[i-1][j-1] + ARR1[i]*ARR2[j] i.e pair ARR1[i] with ARR2[j] and add to it the maximum dot product value till index i-1, j-1.
- dp[i-1][j] + ARR1[i]*0 i.e pair ARR2[j] with some element in ARR1 between index 0 to i - 1 and use a 0 at the ith index.
- In the end return the value of dp[N][M].
Similar problems