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-1]*b[n-1].
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. Therefore b becomes {0, 3, 0, 6, 7}. Maximum dot product = 2*0 + 3*3 + 1*0 + 7*6 + 8*7 = 107.
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Your submissions, results and runtime history live here. Sign in to start your streak.
5 3 2 3 1 7 8 3 6 7
107
