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] 
2*0 + 3*3 + 1*0 + 7*6 + 8*7 = 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] 
1*0 + 2*0 + 3*4 = 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(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ M ≤N ≤ 10^{3}
1 ≤ A[i], B[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def maxDotProduct(self, n, m, A, B):
		# code here

Solutions:
class Solution:

	def solve(self, i, j, n, m, A, B, dp, d):
		if i == n or j == m:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if d > 0:
			dp[i][j] = max(A[i] * B[j] + self.solve(i + 1, j + 1, n, m, A, B, dp, d), self.solve(i + 1, j, n, m, A, B, dp, d - 1))
		else:
			dp[i][j] = A[i] * B[j] + self.solve(i + 1, j + 1, n, m, A, B, dp, d)
		return dp[i][j]

	def maxDotProduct(self, n, m, A, B):
		dp = [[-1 for j in range(m)] for i in range(n)]
		return self.solve(0, 0, n, m, A, B, dp, n - m)


class Solution:

	def maxDotProduct(self, n, m, A, B):

		def fun(i, j):
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				dp[i][j] = A[i] * B[j] + fun(i - 1, j - 1)
				return dp[i][j]
			else:
				dp[i][j] = max(A[i] * B[j] + fun(i - 1, j - 1), fun(i - 1, j))
				return dp[i][j]
		N = n
		M = m
		dp = [[-1 for j in range(N + 1)] for i in range(N + 1)]
		return fun(N - 1, M - 1)


class Solution:

	def maxDotProduct(self, m, n, A, B):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1, 1):
			for j in range(i, m + 1, 1):
				dp[i][j] = max(dp[i - 1][j - 1] + A[j - 1] * B[i - 1], dp[i][j - 1])
		return dp[n][m]


class Solution:

	def maxDotProduct(self, n, m, A, B):

		def product(p1, p2):
			summe = 0
			while p1 < n and p2 < m:
				summe += A[p1] * B[p2]
				p1 += 1
				p2 += 1
			return summe

		def solve(p1, p2):
			if p1 == n and p2 == m or p2 == m:
				return 0
			if p1 == n:
				return float('-inf')
			key = str(p1) + '_' + str(p2)
			if key in dp:
				return dp[key]
			not_zero = A[p1] * B[p2] + solve(p1 + 1, p2 + 1)
			zero = solve(p1 + 1, p2)
			dp[key] = max(zero, not_zero)
			return dp[key]
		diff = n - m
		if diff == 0:
			return product(0, 0)
		else:
			dp = {}
			ans = solve(0, 0)
			return ans


class Solution:

	def maxDotProduct(self, n, m, arr1, arr2):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if i == j:
					dp[i][j] = arr1[i - 1] * arr2[j - 1] + dp[i - 1][j - 1]
				elif i > j:
					dp[i][j] = max(arr1[i - 1] * arr2[j - 1] + dp[i - 1][j - 1], dp[i - 1][j])
		return dp[n][m]


class Solution:

	def maxDotProduct(self, n, m, A, B):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(i, n + 1):
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + A[j - 1] * B[i - 1])
		return dp[-1][-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		(n, m) = (int(n), int(m))
		A = [int(x) for x in input().split()]
		B = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.maxDotProduct(n, m, A, B)
		print(ans)


class Solution:

	def recur(self, ind1, ind2, a, b):
		global dp
		if ind1 < 0 or ind2 < 0:
			return 0
		if ind1 < ind2:
			return 0
		if dp[ind1][ind2]:
			return dp[ind1][ind2]
		z = self.recur(ind1 - 1, ind2, a, b)
		nz = a[ind1] * b[ind2] + self.recur(ind1 - 1, ind2 - 1, a, b)
		dp[ind1][ind2] = max(z, nz)
		return dp[ind1][ind2]

	def maxDotProduct(self, n, m, a, b):
		dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if j >= i:
					dp[i][j] = max(dp[i][j - 1], b[i - 1] * a[j - 1] + dp[i - 1][j - 1])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def solve(self, a, b, i, j, dp):
		if i >= len(a) or j >= len(b):
			return 0
		if not len(a) - i >= len(b) - j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		else:
			dp[i][j] = max(a[i] * b[j] + self.solve(a, b, i + 1, j + 1, dp), self.solve(a, b, i + 1, j, dp))
		return dp[i][j]

	def maxDotProduct(self, n, m, A, B):
		dp = [[-1 for i in range(m)] for j in range(n)]
		ans = self.solve(A, B, 0, 0, dp)
		return ans


class Solution:

	def maxDotProduct(self, n, m, arr1, arr2):
		dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(i, n + 1):
				not_zero = arr2[i - 1] * arr1[j - 1] + dp[i - 1][j - 1]
				zero = dp[i][j - 1]
				dp[i][j] = max(zero, not_zero)
		return dp[m][n]
		memo = {}

		def solve(p1, p2):
			if (p1, p2) in memo:
				return memo[p1, p2]
			if p1 == n and p2 == m or p2 == m:
				return 0
			if p1 == n:
				return float('-inf')
			not_zero = arr1[p1] * arr2[p2] + solve(p1 + 1, p2 + 1)
			zero = solve(p1 + 1, p2)
			memo[p1, p2] = max(zero, not_zero)
			return memo[p1, p2]
		return solve(0, 0)


class Solution:

	def recur(self, ind1, ind2, a, b, z_a):
		global dp
		if ind1 < 0 or ind2 < 0:
			return 0
		if ind1 < ind2:
			return 0
		if dp[ind1][ind2]:
			return dp[ind1][ind2]
		z = self.recur(ind1 - 1, ind2, a, b, z_a - 1)
		nz = a[ind1] * b[ind2] + self.recur(ind1 - 1, ind2 - 1, a, b, z_a)
		dp[ind1][ind2] = max(z, nz)
		return dp[ind1][ind2]

	def maxDotProduct(self, n, m, A, B):
		global dp
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		z_allowed = n - m
		return self.recur(n - 1, m - 1, A, B, z_allowed)


class Solution:

	def maxDotProduct(self, n, m, arr1, arr2):
		memo = {}

		def solve(p1, p2):
			if (p1, p2) in memo:
				return memo[p1, p2]
			if p1 == n and p2 == m or p2 == m:
				return 0
			if p1 == n:
				return float('-inf')
			not_zero = arr1[p1] * arr2[p2] + solve(p1 + 1, p2 + 1)
			zero = solve(p1 + 1, p2)
			memo[p1, p2] = max(zero, not_zero)
			return memo[p1, p2]
		return solve(0, 0)


class Solution:

	def maxDotProduct(self, n, m, c, d):
		a = [[0] * n for i in range(m)]
		a[0][0] = c[0] * d[0]
		for i in range(1, n):
			a[0][i] = max(a[0][i - 1], c[i] * d[0])
		for i in range(1, m):
			a[i][i] = a[i - 1][i - 1] + c[i] * d[i]
			for j in range(i + 1, n):
				a[i][j] = max(a[i][j - 1], a[i - 1][j - 1] + d[i] * c[j])
		return a[m - 1][n - 1]


class Solution:

	def maxDotProduct(self, n, m, A, B):
		if n < m:
			return -1
		if n == m:
			sum = 0
			for i in range(n):
				sum += A[i] * B[i]
			return sum
		if m == 1:
			return max(A) * B[0]
		result = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for j in range(m):
			for i in range(j, n, 1):
				result[i + 1][j + 1] = max(result[i][j + 1], result[i][j] + A[i] * B[j])
		return result[n][m]