Given two arrays nums1 and nums2.
Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.
A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).
 
Example 1:
Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.
Example 2:
Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.
Example 3:
Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.
 
Constraints:

1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        

Solutions:
class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		INF = int(1000000000.0)
		(n, m) = (len(nums1), len(nums2))
		DP = [-INF] * (m + 1)
		NDP = [-INF] * (m + 1)
		for a in range(n):
			for b in range(m):
				el = nums1[a] * nums2[b]
				diag = DP[b]
				NDP[b + 1] = max(el, DP[b + 1], NDP[b], diag, diag + el)
			(DP, NDP) = (NDP, DP)
		return DP[-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		if all((x >= 0 for x in nums1)) and all((y <= 0 for y in nums2)):
			return min(nums1) * max(nums2)
		if all((x <= 0 for x in nums1)) and all((y >= 0 for y in nums2)):
			return max(nums1) * min(nums2)
		accu_max = [0] * (len(nums2) + 1)
		for i in range(len(nums1)):
			last_max = [accu_max[j] + nums1[i] * nums2[j] for j in range(len(nums2))]
			this_accu_max = [0]
			for j in range(len(nums2)):
				this_accu_max.append(max(this_accu_max[-1], last_max[j], accu_max[j + 1]))
			accu_max = this_accu_max
		return accu_max[-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		n1 = len(nums1)
		n2 = len(nums2)
		dp = [[0] * (n2 + 1) for j in range(n1 + 1)]
		for i in range(n1):
			for j in range(n2):
				dp[i + 1][j + 1] = max(dp[i][j] + max(0, nums1[i] * nums2[j]), dp[i][j + 1], dp[i + 1][j])
		if dp[-1][-1] != 0:
			return dp[-1][-1]
		nums1.sort()
		nums2.sort()
		a = nums1[0] if nums1[0] > 0 else nums1[-1]
		b = nums2[0] if nums2[0] > 0 else nums2[-1]
		return a * b


import numpy as np

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		INF = int(1000000000.0)
		(n, m) = (len(nums1), len(nums2))
		DP = np.ones((n, m), dtype=int) * -INF
		DP[0, 0] = nums1[0] * nums2[0]
		for a in range(n):
			for b in range(m):
				el = nums1[a] * nums2[b]
				curr = el
				if a > 0:
					curr = max(curr, DP[a - 1, b])
				if b > 0:
					curr = max(curr, DP[a, b - 1])
				if a > 0 and b > 0:
					prev = DP[a - 1, b - 1]
					curr = max(curr, prev, prev + el)
				DP[a, b] = curr
		return DP[-1, -1]


from functools import lru_cache

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		n = len(nums1)
		m = len(nums2)

		@lru_cache(None)
		def dp(i, j, selected):
			if i == n or j == m:
				return 0 if selected else -1000000000
			a = nums1[i] * nums2[j] + dp(i + 1, j + 1, True)
			b = dp(i, j + 1, selected)
			c = dp(i + 1, j, selected)
			return max(a, b, c)
		return dp(0, 0, False)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		def dp(nums1, nums2, i, j, m, n, dic):
			if i + 1 >= m:
				maximum = None
				for p in range(j, n):
					if maximum == None:
						maximum = nums1[i] * nums2[p]
					else:
						maximum = max(maximum, nums1[i] * nums2[p])
				return maximum
			elif j + 1 >= n:
				maximum = None
				for p in range(i, m):
					if maximum == None:
						maximum = nums1[p] * nums2[j]
					else:
						maximum = max(maximum, nums1[p] * nums2[j])
				return maximum
			if dic[i][j] != None:
				return dic[i][j]
			dic[i][j] = max(nums1[i] * nums2[j], nums1[i] * nums2[j] + dp(nums1, nums2, i + 1, j + 1, m, n, dic), dp(nums1, nums2, i, j + 1, m, n, dic), dp(nums1, nums2, i + 1, j, m, n, dic), dp(nums1, nums2, i + 1, j + 1, m, n, dic))
			return dic[i][j]
		dic = []
		m = len(nums1)
		n = len(nums2)
		for i in range(m):
			dic.append([None] * n)
		return dp(nums1, nums2, 0, 0, m, n, dic)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		@lru_cache(None)
		def cal(i, j):
			if i >= len(nums1) or j >= len(nums2):
				return 0
			return max(nums1[i] * nums2[j] + cal(i + 1, j + 1), cal(i, j + 1), cal(i + 1, j))
		ans = cal(0, 0)
		if ans == 0:
			return max(min(nums1) * max(nums2), min(nums2) * max(nums1))
		else:
			return ans


import numpy as np

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		M = np.zeros((len(nums1), len(nums2)), dtype=np.int)
		M[0][0] = nums1[0] * nums2[0]
		for i in range(1, len(nums1)):
			M[i][0] = max(M[i - 1][0], nums1[i] * nums2[0])
		for j in range(1, len(nums2)):
			M[0][j] = max(M[0][j - 1], nums1[0] * nums2[j])
		for i in range(1, len(nums1)):
			for j in range(1, len(nums2)):
				M[i][j] = max(M[i - 1][j - 1] + nums1[i] * nums2[j], M[i][j - 1], M[i - 1][j], nums1[i] * nums2[j])
		return M[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(n1, n2) = (len(nums1), len(nums2))
		cache = {}

		def process(i, j, k):
			if not (i, j, k) in cache:
				ans = 0
				if i == 0 and j == 0:
					if k == 0:
						ans = nums1[i] * nums2[j]
					else:
						ans = max(nums1[i] * nums2[j], 0)
				elif i == 0:
					ans = max(nums1[i] * nums2[j], process(i, j - 1, k))
				elif j == 0:
					ans = max(nums1[i] * nums2[j], process(i - 1, j, k))
				else:
					ans = max(nums1[i] * nums2[j] + process(i - 1, j - 1, 1), process(i - 1, j, k), process(i, j - 1, k))
				cache[i, j, k] = ans
			return cache[i, j, k]
		return process(n1 - 1, n2 - 1, 0)


mi = -100000000000
dp = [[mi] * 505 for i in range(505)]

def steps(i, j, lis1, lis2):
	best = mi
	if i < 0 or j < 0:
		return 0
	elif dp[i][j] != mi:
		return dp[i][j]
	if i == 0:
		for _ in range(j + 1):
			best = max(lis1[i] * lis2[_], best)
		dp[i][j] = best
		return dp[i][j]
	if j == 0:
		for _ in range(i + 1):
			best = max(lis1[_] * lis2[j], best)
		dp[i][j] = best
		return best
	best = max(steps(i - 1, j, lis1, lis2), steps(i, j - 1, lis1, lis2), lis1[i] * lis2[j] + steps(i - 1, j - 1, lis1, lis2), lis1[i] * lis2[j])
	dp[i][j] = best
	return dp[i][j]

class Solution:

	def maxDotProduct(self, lis1: List[int], lis2: List[int]) -> int:
		n = len(lis1)
		m = len(lis2)
		for i in range(501):
			for j in range(501):
				dp[i][j] = mi
		steps(n - 1, m - 1, lis1, lis2)
		return dp[n - 1][m - 1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(m, n) = (len(nums1), len(nums2))
		INF = -100000000
		dp = [[INF] * (n + 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				dp[i][j] = nums1[i - 1] * nums2[j - 1]
				dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1], dp[i][j] + dp[i - 1][j - 1])
		return dp[m][n]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		def f(nums1, nums2, i, j, D):
			if i == 0 or j == 0:
				return 0
			elif str([i, j]) in D:
				return D[str([i, j])]
			res = max(nums1[i - 1] * nums2[j - 1] + f(nums1, nums2, i - 1, j - 1, D), f(nums1, nums2, i - 1, j, D), f(nums1, nums2, i, j - 1, D))
			D[str([i, j])] = res
			return res
		D = {}
		res = f(nums1, nums2, len(nums1), len(nums2), D)
		if res == 0 and (max(nums1) < 0 and min(nums2) > 0):
			return max(nums1) * min(nums2)
		elif res == 0 and (max(nums2) < 0 and min(nums1) > 0):
			return max(nums2) * min(nums1)
		return res


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = [[0] * len(nums2) for _ in nums1]
		res = -float('inf')
		for i in range(len(nums1)):
			for j in range(len(nums2)):
				if i == 0 or j == 0:
					if i == 0 and j == 0:
						dp[i][j] = nums1[i] * nums2[j]
					elif i == 0:
						dp[i][j] = max(dp[i][j - 1], nums1[i] * nums2[j])
					else:
						dp[i][j] = max(dp[i - 1][j], nums1[i] * nums2[j])
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], nums1[i] * nums2[j], nums1[i] * nums2[j] + dp[i - 1][j - 1])
			res = max(res, dp[i][-1])
		return res


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(n1, n2) = (len(nums1), len(nums2))
		M = [[-100000] * (n2 + 1) for _ in range(n1 + 1)]
		for i in range(n1):
			for j in range(n2):
				M[i + 1][j + 1] = max(M[i][j] + nums1[i] * nums2[j], M[i][j + 1], M[i + 1][j], nums1[i] * nums2[j])
		return M[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		max_dot_product = [nums1[0] * num for num in nums2]
		max_dot_product = list(itertools.accumulate(max_dot_product, max))
		for num1 in nums1[1:]:
			max_dot_product_next = []
			for (i, num2) in enumerate(nums2):
				curr_max = max_dot_product[i]
				if i > 0:
					curr_max = max(curr_max, max(num1 * num2 + max_dot_product[i - 1], max_dot_product_next[i - 1]))
				curr_max = max(curr_max, num1 * num2)
				max_dot_product_next.append(curr_max)
			max_dot_product = max_dot_product_next
		return max(max_dot_product)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		n1 = len(nums1)
		n2 = len(nums2)
		dp = [[0 for _ in range(n2)] for _ in range(n1)]
		for i in range(n1):
			for j in range(n2):
				curr = nums1[i] * nums2[j]
				if i == 0 and j == 0:
					dp[i][j] = curr
				elif i == 0:
					dp[i][j] = max(curr, dp[i][j - 1])
				elif j == 0:
					dp[i][j] = max(curr, dp[i - 1][j])
				else:
					dp[i][j] = max(curr, curr + dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
		return dp[n1 - 1][n2 - 1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		M = len(nums1)
		N = len(nums2)
		dp = [[0] * N for _ in range(M)]
		dp[0][0] = nums1[0] * nums2[0]
		for i in range(1, M):
			dp[i][0] = max(dp[i - 1][0], nums2[0] * nums1[i])
		for i in range(1, N):
			dp[0][i] = max(dp[0][i - 1], nums1[0] * nums2[i])
		for i in range(1, M):
			for j in range(1, N):
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j - 1] + nums1[i] * nums2[j], dp[i - 1][j], dp[i][j - 1], nums1[i] * nums2[j])
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, a: List[int], b: List[int]) -> int:
		nums1 = [0] + a
		nums2 = [0] + b
		(m, n) = (len(nums1), len(nums2))
		dp = [[float('-inf')] * m for _ in range(n)]
		for i in range(1, n):
			for j in range(1, m):
				if nums1[j] * nums2[i] > 0:
					dp[i][j] = max(dp[i - 1][j - 1] + nums1[j] * nums2[i], dp[i][j - 1], dp[i - 1][j], nums1[j] * nums2[i])
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j], nums1[j] * nums2[i])
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1, nums2) -> int:
		(n, m) = (len(nums1), len(nums2))
		dp = [[0 for _ in range(m)] for _ in range(n)]
		dp[0][0] = nums1[0] * nums2[0]
		for j in range(1, m):
			dp[0][j] = max(dp[0][j - 1], nums1[0] * nums2[j])
		for i in range(1, n):
			dp[i][0] = max(dp[i - 1][0], nums1[i] * nums2[0])
		for i in range(1, n):
			for j in range(1, m):
				dp[i][j] = max(nums1[i] * nums2[j], dp[i - 1][j - 1] + nums1[i] * nums2[j], dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
		return dp[n - 1][m - 1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		n1: int = len(nums1)
		n2: int = len(nums2)
		dp: List[List[int]] = [[float('-inf') for _ in range(n2 + 1)] for _ in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1])
		return dp[n1][n2]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = [[0 for i in range(len(nums2) + 1)] for j in range(len(nums1) + 1)]
		for i in range(len(nums1)):
			for j in range(len(nums2)):
				dp[i + 1][j + 1] = max([dp[i][j] + nums1[i] * nums2[j], dp[i + 1][j], dp[i][j + 1]])
		return dp[len(nums1)][len(nums2)] if dp[len(nums1)][len(nums2)] > 0 else max([max(nums1) * max(nums2), min(nums1) * min(nums2), max(nums1) * min(nums2), min(nums1) * max(nums2)])


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = [[0] * len(nums2) for _ in range(len(nums1))]
		for i in range(len(nums1)):
			for j in range(len(nums2)):
				if i == 0 and j == 0:
					dp[i][j] = nums1[0] * nums2[0]
					continue
				prod = nums1[i] * nums2[j]
				if i == 0:
					dp[i][j] = max(dp[i][j - 1], prod)
					continue
				if j == 0:
					dp[i][j] = max(dp[i - 1][j], prod)
					continue
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + prod, prod)
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		m = len(nums1)
		n = len(nums2)
		dp = [[-float('inf')] * (n + 1) for i in range(m + 1)]
		res = -float('inf')
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1], nums1[i - 1] * nums2[j - 1])
		for row in dp:
			for x in row:
				res = max(res, x)
		return res


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		m = len(nums1)
		n = len(nums2)
		dp = [[0] * n for i in range(m)]
		for i in range(m):
			for j in range(n):
				if i == 0 and j == 0:
					dp[i][j] = nums1[i] * nums2[j]
				elif i == 0:
					dp[i][j] = max(dp[i][j - 1], nums1[i] * nums2[j])
				elif j == 0:
					dp[i][j] = max(dp[i - 1][j], nums1[i] * nums2[j])
				else:
					temp = nums1[i] * nums2[j]
					dp[i][j] = max(temp, dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + temp)
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		N = len(nums1)
		M = len(nums2)
		if max(nums1) < 0 and min(nums2) > 0:
			return max(nums1) * min(nums2)
		if max(nums2) < 0 and min(nums1) > 0:
			return min(nums1) * max(nums2)
		dp = [[0 for i in range(M + 1)] for j in range(N + 1)]
		for i in range(N):
			for j in range(M):
				dp[i + 1][j + 1] = max(dp[i][j] + nums1[i] * nums2[j], dp[i][j + 1], dp[i + 1][j])
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = [[0] * len(nums2) for _ in range(len(nums1))]
		dp[0][0] = max(0, nums1[0] * nums2[0])
		for i in range(0, len(nums1)):
			for j in range(0, len(nums2)):
				if i > 0 and j > 0:
					dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + nums1[i] * nums2[j])
				else:
					if j > 0 and i == 0:
						dp[i][j] = max(dp[i][j - 1], nums1[i] * nums2[j])
					if i > 0 and j == 0:
						dp[i][j] = max(dp[i - 1][j], nums1[i] * nums2[j])
		ans = max([max(x) for x in dp])
		if ans > 0:
			return ans
		else:
			best = -9999999
			for k in nums1:
				for l in nums2:
					best = max(best, k * l)
			return best


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		N = len(nums1)
		M = len(nums2)
		dp = [[0] * M for _ in range(N)]
		dp[0][0] = nums1[0] * nums2[0]
		res = dp[0][0]
		big = nums1[0] >= 0
		acc = nums2[0]
		for (i, x) in enumerate(nums2[1:]):
			if big and x > acc:
				acc = x
			elif not big and x < acc:
				acc = x
			dp[0][i + 1] = acc * nums1[0]
			res = max(res, dp[0][i + 1])
		big = nums2[0] >= 0
		acc = nums1[0]
		for (i, x) in enumerate(nums1[1:]):
			if big and x > acc:
				acc = x
			elif not big and x < acc:
				acc = x
			dp[i + 1][0] = acc * nums2[0]
			res = max(res, dp[i + 1][0])
		for i in range(1, N):
			for j in range(1, M):
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], nums1[i] * nums2[j] + max(0, dp[i - 1][j - 1]))
				res = max(res, dp[i][j])
		return res


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = [[-sys.maxsize - 1 for i in range(len(nums2) + 1)] for j in range(len(nums1) + 1)]
		for i in range(1, len(nums1) + 1):
			for j in range(1, len(nums2) + 1):
				t = nums1[i - 1] * nums2[j - 1]
				dp[i][j] = max({dp[i - 1][j - 1] + t, t, dp[i - 1][j], dp[i][j - 1]})
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(n1, n2) = (len(nums1), len(nums2))
		mem = [[float('-inf')] * (n2 + 1) for _ in range(n1 + 1)]
		mem[0][0] = 0
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				mem[i][j] = max(mem[i][j], max(nums1[i - 1] * nums2[j - 1] + max(0, mem[i - 1][j - 1]), mem[i][j - 1], mem[i - 1][j]))
		return mem[n1][n2]

		@lru_cache
		def dp(i1, j1, i2, j2):
			if i1 > j1 or i2 > j2:
				return 0
			if i1 == j1 and i2 == j2:
				return nums1[i1] * nums2[i2]
			if mem[i1][j1][i2][j2] != float('-inf'):
				return mem[i1][j1][i2][j2]
			ans = float('-inf')
			for k1 in range(i1, j1 + 1):
				for k2 in range(i2, j2 + 1):
					ans = max(ans, max(0, nums1[k1] * nums2[k2]) + dp(i1, k1 - 1, i2, k2 - 1) + dp(k1 + 1, j1, k2 + 1, j2))
			mem[i1][j1][i2][j2] = ans
			return ans
		return dp(0, n1 - 1, 0, n2 - 1)


class Solution:

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


from functools import lru_cache

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(l1, l2) = (len(nums1), len(nums2))
		if all([x < 0 for x in nums1]) and all([x > 0 for x in nums2]):
			return max(nums1) * min(nums2)
		if all([x > 0 for x in nums1]) and all([x < 0 for x in nums2]):
			return min(nums1) * max(nums2)

		@lru_cache(None)
		def dfs(i1, i2):
			if i1 == l1 or i2 == l2:
				return 0
			return max(dfs(i1 + 1, i2), dfs(i1, i2 + 1), nums1[i1] * nums2[i2] + dfs(i1 + 1, i2 + 1))
		return dfs(0, 0)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		@lru_cache(None)
		def dp(i, j):
			if i < 0 or j < 0:
				return -float('inf')
			return max(nums1[i] * nums2[j], nums1[i] * nums2[j] + dp(i - 1, j - 1), dp(i, j - 1), dp(i - 1, j))
		return dp(len(nums1) - 1, len(nums2) - 1)


def max_dot_product(A, B):
	mem = {}
	for i in range(len(A)):
		for j in range(len(B)):
			if i == j == 0:
				ans = A[i] * B[j]
			elif i == 0:
				ans = max(A[i] * B[j], mem[i, j - 1])
			elif j == 0:
				ans = max(A[i] * B[j], mem[i - 1, j])
			else:
				ans = max(A[i] * B[j], A[i] * B[j] + mem[i - 1, j - 1], mem[i, j - 1], mem[i - 1, j])
			mem[i, j] = ans
	return mem[len(A) - 1, len(B) - 1]

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		return max_dot_product(nums1, nums2)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(n, m) = (len(nums1), len(nums2))
		if max(nums1) < 0 and min(nums2) > 0 or (max(nums2) < 0 and min(nums1) > 0):
			return max(max(nums1) * min(nums2), max(nums2) * min(nums1))
		import functools

		@functools.lru_cache(None)
		def DP(i, j):
			if i == n or j == m:
				return 0
			if nums1[i] * nums2[j] > 0:
				return max(nums1[i] * nums2[j] + DP(i + 1, j + 1), DP(i, j + 1), DP(i + 1, j))
			else:
				return max(DP(i + 1, j + 1), DP(i, j + 1), DP(i + 1, j))
		return DP(0, 0)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = []
		for i in range(len(nums1)):
			dp.append([])
			for j in range(len(nums2)):
				dp[i].append(0)
		for i in range(len(nums1)):
			for j in range(len(nums2)):
				dp[i][j] = nums1[i] * nums2[j]
				if i and j:
					dp[i][j] += max(dp[i - 1][j - 1], 0)
				if i:
					dp[i][j] = max(dp[i][j], dp[i - 1][j])
				if j:
					dp[i][j] = max(dp[i][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(mx, m, n) = (-math.inf, len(nums1), len(nums2))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for (i, num1) in enumerate(nums1):
			for (j, num2) in enumerate(nums2):
				p = num1 * num2
				mx = max(p, mx)
				p = max(p, 0)
				dp[i + 1][j + 1] = max(dp[i][j] + p, dp[i + 1][j], dp[i][j + 1])
		return mx if mx <= 0 else dp[m][n]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		if not nums1:
			return 0
		cache = [[0 for _ in nums2] for _ in nums1]
		cache[-1][-1] = nums1[-1] * nums2[-1]
		for i in range(len(nums1) - 2, -1, -1):
			cache[i][-1] = max(nums1[i] * nums2[-1], cache[i + 1][-1])
		for i in range(len(nums2) - 2, -1, -1):
			cache[-1][i] = max(nums1[-1] * nums2[i], cache[-1][i + 1])
		for i in range(len(nums1) - 2, -1, -1):
			for j in range(len(nums2) - 2, -1, -1):
				cache[i][j] = max(nums1[i] * nums2[j] + max(cache[i + 1][j + 1], 0), cache[i + 1][j], cache[i][j + 1])
		return cache[0][0]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dp = collections.defaultdict(lambda : -math.inf)
		for (i, j) in product(range(len(nums1)), range(len(nums2))):
			(x, y) = (nums1[i] * nums2[j], dp[i - 1, j - 1])
			m = max(x, y) if x < 0 and y < 0 else max(x, 0) + max(y, 0)
			dp[i, j] = max(dp[i - 1, j], dp[i, j - 1], m)
		return dp[len(nums1) - 1, len(nums2) - 1]


from functools import lru_cache

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		@lru_cache(None)
		def helper(i, j):
			if i == 0 or j == 0:
				return -math.inf
			return max(helper(i - 1, j - 1), helper(i, j - 1), helper(i - 1, j), max(helper(i - 1, j - 1), 0) + nums1[i - 1] * nums2[j - 1])
		return helper(len(nums1), len(nums2))


import sys

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		M = len(nums1)
		N = len(nums2)
		dp = [[-sys.maxsize] * N for _ in range(M)]
		max_p = -sys.maxsize
		for (i, num) in enumerate(nums2):
			max_p = max(max_p, nums1[0] * nums2[i])
			dp[0][i] = max_p
		max_p = -sys.maxsize
		for (i, num) in enumerate(nums1):
			max_p = max(max_p, nums1[i] * nums2[0])
			dp[i][0] = max_p
		for i in range(1, M):
			for j in range(1, N):
				x = nums1[i] * nums2[j]
				dp[i][j] = max(x + max(dp[i - 1][j - 1], 0), dp[i - 1][j], dp[i][j - 1])
		return dp[M - 1][N - 1]


class Solution:

	def maxDotProduct(self, nums1, nums2):
		if all((x >= 0 for x in nums1)) and all((y <= 0 for y in nums2)):
			return min(nums1) * max(nums2)
		if all((x <= 0 for x in nums1)) and all((y >= 0 for y in nums2)):
			return max(nums1) * min(nums2)
		(a, b) = (len(nums1), len(nums2))
		dp = [[0 for _ in range(b)] for _ in range(a)]
		for i in range(a):
			for j in range(b):
				dp[i][j] = nums1[i] * nums2[j]
				if i:
					dp[i][j] = max(dp[i][j], dp[i - 1][j])
				if j:
					dp[i][j] = max(dp[i][j], dp[i][j - 1])
				if i and j:
					dp[i][j] = max(dp[i][j], nums1[i] * nums2[j] + dp[i - 1][j - 1])
		return dp[a - 1][b - 1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(a, b) = ([None] + nums1, [None] + nums2)
		(m, n) = (len(a), len(b))
		dp = [[-math.inf] * n for _ in range(m)]
		for i in range(1, m):
			for j in range(1, n):
				here = a[i] * b[j]
				dp[i][j] = max(here, dp[i - 1][j - 1] + max(here, 0), dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		arr = [[-math.inf for i in range(len(nums1) + 1)] for j in range(len(nums2) + 1)]
		for i in range(len(nums2) + 1):
			arr[i][0] = -math.inf
		for i in range(len(nums1) + 1):
			arr[0][i] = -math.inf
		maxc = nums2[0] * nums1[0]
		for i in range(len(nums2) + 1)[1:]:
			for j in range(len(nums1) + 1)[1:]:
				arr[i][j] = max(arr[i][j], arr[i][j - 1])
				arr[i][j] = max(arr[i][j], arr[i - 1][j])
				arr[i][j] = max(arr[i][j], max(arr[i - 1][j - 1], 0) + nums2[i - 1] * nums1[j - 1])
				if arr[i][j] > maxc:
					maxc = arr[i][j]
		return maxc


import sys
from typing import List

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		result = -sys.maxsize
		len1 = len(nums1)
		len2 = len(nums2)
		dp = [[-sys.maxsize for j in range(len2)] for i in range(len1)]
		for i in range(0, len1):
			for j in range(0, len2):
				dp[i][j] = nums1[i] * nums2[j]
				if i > 0:
					dp[i][j] = max(dp[i][j], dp[i - 1][j])
				if j > 0:
					dp[i][j] = max(dp[i][j], dp[i][j - 1])
				if i > 0 and j > 0:
					dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + nums1[i] * nums2[j])
				result = max(result, dp[i][j])
				pass
			pass
		return result


class Solution:

	def maxDotProduct(self, nums1, nums2) -> int:
		(n, m) = (len(nums1), len(nums2))
		dp1 = [[-float('inf')] * m for _ in range(n)]
		dp2 = [[-float('inf')] * m for _ in range(n)]
		for i in range(n):
			for j in range(m):
				dp1[i][j] = nums1[i] * nums2[j]
				if i != 0 and j != 0:
					dp1[i][j] = max(dp1[i][j], dp2[i - 1][j - 1] + nums1[i] * nums2[j])
				dp2[i][j] = dp1[i][j]
				if i != 0:
					dp2[i][j] = max(dp2[i][j], dp2[i - 1][j])
				if j != 0:
					dp2[i][j] = max(dp2[i][j], dp2[i][j - 1])
		ans = -float('inf')
		for i in range(n):
			for j in range(m):
				ans = max(ans, dp2[i][j])
		return ans


class Solution:

	def maxDotProduct(self, nums1, nums2):
		m = len(nums1)
		n = len(nums2)
		mem = [[None] * n for i in range(m)]
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				mem[i][j] = nums1[i] * nums2[j]
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				max_ = mem[i + 1][j + 1] if i + 1 < m and j + 1 < n else -1001
				mem[i][j] = max(mem[i][j] + max_, max(mem[i][j], max_))
				mem[i][j] = max(mem[i][j], mem[i][j + 1] if j < n - 1 else -1001)
				mem[i][j] = max(mem[i][j], mem[i + 1][j] if i < m - 1 else -1001)
		return mem[0][0]


MAX_VAL = -10 ** 9 - 7

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		num_rows = len(nums1) + 1
		num_cols = len(nums2) + 1
		dp = []
		for i in range(num_rows):
			dp.append([MAX_VAL] * num_cols)
		for i in range(1, num_rows):
			for j in range(1, num_cols):
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1], nums1[i - 1] * nums2[j - 1])
		return dp[-1][-1]


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		L1 = len(nums1)
		L2 = len(nums2)
		temp = [[u * v for v in nums2] for u in nums1]
		dic = {}
		dic[0, 0] = temp[0][0]

		def search(i, j):
			if (i, j) in dic:
				return dic[i, j]
			if i == 0:
				dic[0, j] = max(search(0, j - 1), temp[0][j])
				return dic[i, j]
			elif j == 0:
				dic[i, 0] = max(search(i - 1, 0), temp[i][0])
				return dic[i, 0]
			else:
				dic[i, j] = max(search(i - 1, j), search(i, j - 1), temp[i][j] + search(i - 1, j - 1), temp[i][j])
				return dic[i, j]
		return search(L1 - 1, L2 - 1)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		(N, M) = (len(nums1), len(nums2))
		dp = [[None] * M for _ in range(N)]

		def solve(i, j):
			if i >= N or j >= M:
				return 0
			if dp[i][j] is None:
				dp[i][j] = max(nums1[i] * nums2[j] + solve(i + 1, j + 1), solve(i + 1, j), solve(i, j + 1), solve(i + 1, j + 1))
			return dp[i][j]
		result = solve(0, 0)
		if result == 0 and 0 not in nums1 + nums2:
			if nums1[0] < 0:
				return max(nums1) * min(nums2)
			else:
				return min(nums1) * max(nums2)
		else:
			return result


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		dic = {}
		dic[0, 0] = nums1[0] * nums2[0]

		def search(i, j):
			a = nums1[i] * nums2[j]
			if (i, j) in dic:
				return dic[i, j]
			if i == 0:
				dic[0, j] = max(search(0, j - 1), a)
				return dic[i, j]
			elif j == 0:
				dic[i, 0] = max(search(i - 1, 0), a)
				return dic[i, 0]
			else:
				dic[i, j] = max(search(i - 1, j), search(i, j - 1), a + search(i - 1, j - 1), a)
				return dic[i, j]
		return search(len(nums1) - 1, len(nums2) - 1)


from functools import lru_cache

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		@lru_cache(None)
		def dot(i, j):
			if i == N1 or j == N2:
				return -sys.maxsize
			ans = nums1[i] * nums2[j]
			ans = max(ans, ans + dot(i + 1, j + 1), dot(i, j + 1), dot(i + 1, j), dot(i + 1, j + 1))
			return ans
		(N1, N2) = (len(nums1), len(nums2))
		return dot(0, 0)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		m = len(nums1)
		n = len(nums2)
		dp = [[-math.inf] * n for _ in range(m)]
		for i in range(0, m):
			for j in range(0, n):
				if i > 0:
					dp[i][j] = max(dp[i][j], dp[i - 1][j])
				if j > 0:
					dp[i][j] = max(dp[i][j], dp[i][j - 1])
				dp[i][j] = max(dp[i][j], nums1[i] * nums2[j])
				if i > 0 and j > 0 and (dp[i - 1][j - 1] > 0):
					dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + nums1[i] * nums2[j])
		return dp[m - 1][n - 1]


def maxsub(a, b):
	dp = [[0 for x in range(len(b))] for x in range(len(a))]
	for i in range(len(a)):
		for j in range(len(b)):
			dp[i][j] = a[i] * b[j]
			if i - 1 >= 0:
				dp[i][j] = max(dp[i][j], dp[i - 1][j])
			if j - 1 >= 0:
				dp[i][j] = max(dp[i][j], dp[i][j - 1])
			if i - 1 >= 0 and j - 1 >= 0:
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i] * b[j])
	return dp[-1][-1]

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		return maxsub(nums1, nums2)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		return dp_with_recursion(nums1, nums2)

def dp_with_recursion(a, b):

	@lru_cache(maxsize=None)
	def recursion(i, j, is_empty=True):
		if i < 0 or j < 0:
			return float('-inf') if is_empty else 0
		return max(recursion(i, j - 1, is_empty), recursion(i - 1, j, is_empty), recursion(i - 1, j - 1, False) + a[i] * b[j])
	return recursion(len(a) - 1, len(b) - 1)


class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
		a = [[-1 for _ in range(len(nums2))] for _ in range(len(nums1))]

		def dp(x, y):
			if len(nums1) == x or len(nums2) == y:
				return -float('inf')
			if a[x][y] != -1:
				return a[x][y]
			else:
				a[x][y] = max(dp(x + 1, y), dp(x, y + 1), dp(x + 1, y + 1) + nums1[x] * nums2[y], nums1[x] * nums2[y])
				return a[x][y]
		return dp(0, 0)


from functools import lru_cache

class Solution:

	def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

		@lru_cache(None)
		def solve(i, j, c):
			if i == len(nums1) or j == len(nums2):
				if c:
					return 0
				return float('-inf')
			return max(solve(i + 1, j, c), solve(i, j + 1, c), nums1[i] * nums2[j] + solve(i + 1, j + 1, True))
		return solve(0, 0, False)