Given two arrays A and B of positive integers of size N and M where N >= M, the task is to maximize the dot product by inserting zeros in the second array but you cannot disturb the order of elements.
Dot Product of array A and B of size N is A[0]B[0] + A[1]B[1]+....A[N]B[N].
Example 1:
Input: N = 5, A[] = {2, 3, 1, 7, 8}
M = 3, B[] = {3, 6, 7}
Output: 107
Explanation: We get maximum dot product
after inserting 0 at first and third
positions in second array.
Maximum Dot Product : = A[i] * B[j]
20 + 33 + 10 + 76 + 87 = 107
Example 2:
Input: N = 3, A[] = {1, 2, 3}
M = 1, B[] = {4}
Output: 12
Explanation: We get maximum dot product
after inserting 0 at first and second
positions in second array.
Maximum Dot Product : = A[i] * B[j]
10 + 20 + 34 = 12
Your Task:
You don't need to read input or print anything. Complete the function maxDotProduct() which takes N, M, array A and B as input parameters and returns the maximum value.
Expected Time Complexity: O(NM)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ M ≤N ≤ 10^{3}
1 ≤ A[i], B[i] ≤ 10^{3}

见题面

见题面