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: interview

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:
        
        # DP(a=index of last, b=index of last) = max of:
        #   DP(a-1, b)
        #   DP(a-1, i) + nums1[a] * max_or_min(nums2[i+1:b+1])
        #   same for b
        
        INF = int(1e9)
        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])
        # print(dp)  
        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:
        
        # DP(a=index of last, b=index of last) = max of:
        #   DP(a-1, b)
        #   DP(a-1, i) + nums1[a] * max_or_min(nums2[i+1:b+1])
        #   same for b
        
        INF = int(1e9)
        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])
            # print(M)
        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)
        # dp = [float(\"-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] = max(dp[i-1][j], dp[i][j-1], max(0, dp[i-1][j-1]) + nums1[i] * nums2[j])
        # return dp[m][n]
        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])
        #print(dp)
        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
            #print(num1, max_dot_product)
        #print(max_dot_product)
        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[i][j] max dot product of nums[:i+1][:j+1]
        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(x, y) = max([nums1[x]*nums2[y] + dp(x-1, y-1), dp(x-1, y), dp(x, y-1)])
        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:
        
        dp=[[0 for _ in range(len(nums2))] for _ in range(len(nums1))]
        
        dp[-1][-1]=nums1[-1]*nums2[-1]
        for i in range(len(nums1)-2,-1,-1):
            dp[i][-1]=max(dp[i+1][-1],nums1[i]*nums2[-1])
        
        for i in range(len(nums2)-2,-1,-1):
            dp[-1][i]=max(dp[-1][i+1],nums1[-1]*nums2[i])
        
        for i in range(len(nums1)-2,-1,-1):
            for j in range(len(nums2)-2,-1,-1):
                dp[i][j]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1],dp[i+1][j+1]+(nums1[i]*nums2[j]),nums1[i]*nums2[j])
        return dp[0][0]
                
                
        
        
#         def backtrack(arr,ind,curr,sol):
#             if curr:
#                 sol[len(curr)-1].append(curr)
#             for i in range(ind,len(arr)):
#                 backtrack(arr,i+1,curr+[arr[i]],sol)
        
#         subs1=[[] for _ in range(len(nums1))]
#         subs2=[[] for _ in range(len(nums2))]
        
#         backtrack(nums1,0,[],subs1)
#         backtrack(nums2,0,[],subs2)
        
#         mx=float(\"-inf\")

#         for i in range(min(len(nums1),len(nums2))):
#             for j in range(len(subs1[i])):
#                 for k in range(len(subs2[i])):
#                     ans=0
#                     for l in range(i+1):
#                         ans+=subs1[i][j][l]*subs2[i][k][l]
#                     mx=max(mx,ans)
#         return mx
                        


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])
                #print(i,j,dp[i][j])
                
      #  print(dp)
      #  print(max(dp))
            
        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:
        n1=len(nums1)
        n2=len(nums2)
        dp=[[[0,0] for i in range(n2)] for j in range(n1)]
        
        for i in range(n1):
            for j in range(n2):
                if i==0:
                    if j==0:
                        dp[i][j]=nums1[i]*nums2[j]
                        
                    else:
                        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:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1],nums1[i]*nums2[j]+dp[i-1][j-1],dp[i-1][j-1],nums1[i]*nums2[j])
                    
                    
        return dp[-1][-1]
                


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]})
        # print(dp)
        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]))
        # print(mem)
        return mem[n1][n2]
        
        # mem = [[[[float('-inf')] * n2 for j in range(n2)] for i1 in range(n1)] for i2 in range(n1)]
        @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]

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]

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        m = len(nums2)
        dp = [[0] * m for i 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):
                prod = nums1[i] * nums2[j]
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + (prod if prod > 0 else 0), prod)
        # print(dp)
        return dp[n - 1][m - 1]

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        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]


class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        d = [[0] * (n2+1) for _ in range(n1+1)]
        inf = -float('inf')
        for i in range(n1):
            for j in range(n2):
                d[i][j] = max(d[i-1][j] if i else inf,d[i][j-1] if j else inf, nums1[i] * nums2[j] + (d[i-1][j-1] if d[i-1][j-1] > 0 else 0))
        return d[n1-1][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 > 0 and j > 0:
                    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)

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0 for _ in range(len(nums2))] for x in range(len(nums1))]
        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]


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, 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, 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]


class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        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]

class Solution:
  def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
    # TC: O(MN), SC: O(MN), refr. longest common sequence, Q1035
    m, n = len(nums1), len(nums2)
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
      for j in range(n):
        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[m - 1][n - 1]

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:
        dp = [[0] * len(nums2) for _ in range(len(nums1))]
        
        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(0, dp[i-1][j-1])
                    
                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:
#         Target: We want to calculate the maximal dot product for nums1[0:i] and nums2[0:j]
# Base case
# When i == 0 or j == 0, we return -inf. (Because this is an empty case, which is intolerable)
# State Transition, for any i > 0 and j > 0, there are 4 possibilities
# nums1[i - 1] is not selected, dp[i][j] = dp[i - 1][j]
# nums2[j - 1] is not selected, dp[i][j] = dp[i][j - 1]
# Neither nums1[i - 1] or nums2[j - 1] is selected, dp[i][j] = dp[i - 1][j - 1]
# Both nums1[i - 1] and nums2[j - 1] are selected, dp[i][j] = max(dp[i - 1][j - 1], 0) + nums1[i - 1] * nums2[j - 1]
# Since we already selected one pair (nums1[i - 1], nums2[j - 1]), we can assume the minimal proceeding value is 0
        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]
             
        # n, m = len(nums1), len(nums2)
        # dp = [-math.inf] * (m + 1)
        # for i in range(1, n + 1):
        #     dp, old_dp = [-math.inf], dp
        #     for j in range(1, m + 1):
        #         dp += max(
        #             old_dp[j], # not select i
        #             dp[-1], # not select j
        #             old_dp[j - 1], # not select either
        #             max(old_dp[j - 1], 0) + nums1[i - 1] * nums2[j - 1], # select both
        #         ),
        # return dp[-1]     


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:
        n, m = len(nums1), len(nums2)
        dp = [[0] * (m) for i in range(n)]
        for i in range(n):
            for j in range(m):
                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:
        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)]

# class Solution:
#     def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
#         # max over three different situations
#         # use memoization to avoid repeating. subproblems

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))

# DP

import sys

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        # DP[i][j] -- max-dot-prod(nums1[0:i], nums[0:j])
        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: List[int], nums2: List[int]) -> int:
        dp = []
        maxes = []
        for i in range(len(nums1)):
            dp.append([])
            maxes.append([])
            for j in range(len(nums2)):
                dp[i].append(0)
                maxes[i].append(0)
        for i in range(len(nums1)):
            dp[i][0] = nums1[i] * nums2[0]
            if i > 0:
                dp[i][0] = max(dp[i][0], dp[i-1][0])
        for j in range(len(nums2)):
            dp[0][j] = nums1[0] * nums2[j]
            if j > 0:
                dp[0][j] = max(dp[0][j], dp[0][j-1])
        for i in range(1, len(nums1)):
            for j in range(1, len(nums2)):
                dp[i][j] = max(dp[i-1][j-1] + nums1[i] * nums2[j],
                               nums1[i] * nums2[j])
                dp[i][j] = max(dp[i][j], dp[i-1][j])
                dp[i][j] = max(dp[i][j-1], dp[i][j])
        return dp[-1][-1]
#         dp = []
#         maxes = []
#         for i in range(len(nums1)):
#             dp.append([])
#             maxes.append([])
#             for j in range(len(nums2)):
#                 dp[i].append(0)
#                 maxes[i].append(0)
        
#         for i in range(len(nums1)):
#             dp[i][0] = nums1[i] * nums2[0]
#             maxes[i][0] = nums1[i] * nums2[0]
#             if i > 0:
#                 maxes[i][0] = max(maxes[i-1][0], nums1[i] * nums2[0])
#         for j in range(len(nums2)):
#             dp[0][j] = nums1[0] * nums2[j]
#             maxes[0][j] = nums1[0] * nums2[j]
#             if j > 0:
#                 maxes[0][j] = max(maxes[0][j-1], nums1[0] * nums2[j])
                
#         for i in range(1, len(nums1)):
#             for j in range(1, len(nums2)):
#                 dp[i][j] = max(maxes[i-1][j-1] + nums1[i] * nums2[j],
#                               nums1[i] * nums2[j])
#                 maxes[i][j] = max(maxes[i-1][j-1], maxes[i-1][j])
#                 maxes[i][j] = max(maxes[i][j], maxes[i][j-1])
#                 maxes[i][j] = max(maxes[i][j], dp[i][j])
        
#         return maxes[i][j]


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:
        n = len(nums1)
        m = len(nums2)
        dp = [[0 for _ in range(m)] for _ in range(n)]
        dp[0][0] = nums1[0]*nums2[0]
        for i in range(1,m):
            dp[0][i] = max(dp[0][i-1],nums1[0]*nums2[i])
        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0],nums2[0]*nums1[i])
        for i in range(1,n):
            for j in range(1,m):
                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],nums1[i]*nums2[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))]
        
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                dp[i][j] = nums1[i] * nums2[j]
                if i >= 1:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j])
                if j >= 1:
                    dp[i][j] = max(dp[i][j], dp[i][j - 1])
                if i >= 1 and j >= 1:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] +  nums1[i] * nums2[j])
                
        return dp[len(nums1) - 1][len(nums2) - 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:
        m, n = len(nums1), len(nums2)
        dp = [[-math.inf]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                a = dp[i-1][j]
                b = dp[i][j-1]
                c = max(dp[i-1][j-1], nums1[i-1]*nums2[j-1], dp[i-1][j-1]+nums1[i-1]*nums2[j-1])
                dp[i][j] = max(a, b, c)
        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: List[int], nums2: List[int]) -> int:
        
        
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [[0] * (n2) for j in range(n1)]
        for i in range(n1):
            for j in range(n2):
                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]
        #         dp[i+1][j+1] = max(dp[i][j] + max(0, nums1[i] * nums2[j]), dp[i][j+1], dp[i+1][j])
        # # print(dp)  
        # 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
                
                
                
        
        


class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m,n=len(nums1),len(nums2)
        dp=[[0]*n for _ in range(m)]
        #(i,j)到当前位置的最大子序列乘积和
        for i in range(m):
            for j in range(n):
                dp[i][j]=nums1[i]*nums2[j]   
                if i>0 and j>0:   #此时判断是否与前边连接
                    dp[i][j]+=max(0,dp[i-1][j-1])
                #当前i,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])
        return dp[-1][-1]
            
#类似于72：编辑距离
#dp[i][j]代表nums1到i位，nums2到j位的最大乘积和
#由于是子序列，要判断取i还是取j,以及前边的子序列要不要取


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


import numpy as np
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        
        # DP(a=index of last, b=index of last) = max of:
        #   DP(a-1, b)
        #   DP(a-1, i) + nums1[a] * max_or_min(nums2[i+1:b+1])
        #   same for b
        
        INF = int(1e9)
        n, m = len(nums1), len(nums2)

        DP = np.ones((n + 1, m + 1), dtype=int) * -INF

        for a in range(n):
            for b in range(m):
                
                el = nums1[a] * nums2[b]

                diag = DP[a, b]

                DP[a + 1, b + 1] = max(el, DP[a, b + 1], DP[a + 1, b], diag, diag + el)
                    
        return DP[-1, -1]

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]
        #myPrint(mem)

        for i in range(m-1,-1,-1):
            #max_ = mem[i+1][n-1] if i<m-1 else -1001
            for j in range(n-1,-1,-1):
                #print('i,j : ' ,i,j)
                #if mem[i][j] < 0 and max_ < 0: 
                #    mem[i][j] = max(mem[i][j], max_)
                #else:
                #print('here2 :', max_)
                #mem[i][j] = max(mem[i][j] + max_, max(mem[i][j], max_))
                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_))
                #print('here : ', mem[i][j])
                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)
                #max_ = max(max_, mem[i+1][j] if i<m-1 else -1001)
                #myPrint(mem)
        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, A: List[int], B: List[int]) -> int:
        n=len(A)
        m=len(B)
        dp=[[0]*(m) for _ 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]            
                
        
       
    '''
    
    
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
0 0  *  2 3
[[6, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

0 1  *  2 0
[[6, 6, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
0 2  *  2 -6
[[6, 6, 6], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
----------------------
1 0  *  1 3
[[6, 6, 6], [6, 0, 0], [0, 0, 0], [0, 0, 0]]
1 1  *  1 0
[[6, 6, 6], [6, 6, 0], [0, 0, 0], [0, 0, 0]]
1 2  *  1 -6
[[6, 6, 6], [6, 6, 6], [0, 0, 0], [0, 0, 0]]
----------------------
2 0  *  -2 3
[[6, 6, 6], [6, 6, 6], [6, 0, 0], [0, 0, 0]]
2 1  *  -2 0
[[6, 6, 6], [6, 6, 6], [6, 6, 0], [0, 0, 0]]
2 2  *  -2 -6
[[6, 6, 6], [6, 6, 6], [6, 6, 18], [0, 0, 0]]
----------------------
3 0  *  5 3
[[6, 6, 6], [6, 6, 6], [6, 6, 18], [15, 0, 0]]
3 1  *  5 0
[[6, 6, 6], [6, 6, 6], [6, 6, 18], [15, 15, 0]]
3 2  *  5 -6
[[6, 6, 6], [6, 6, 6], [6, 6, 18], [15, 15, 18]]
----------------------
    
    
    
    
    
    
    
    [0, 0, 0], 
    [0, 0, 0], 
    [0, 0, 0], 
    [0, 0, 0]

    
    
    '''


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:
        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):
            a=temp[i][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(L1-1,L2-1)

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        
        # fuck!!! I finally did a DP problem!!! CRYING
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [[0] * (n2) for j in range(n1)]
        for i in range(n1):
            for j in range(n2):
                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]
        #         dp[i+1][j+1] = max(dp[i][j] + max(0, nums1[i] * nums2[j]), dp[i][j+1], dp[i+1][j])
        # # print(dp)  
        # 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
                
                
                
        
        


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:
        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]
                if dp[i-1][j-1] == -sys.maxsize-1:
                    dp[i][j] = max(t,max(dp[i-1][j], dp[i][j-1]))
                else:
                    dp[i][j] = max(dp[i-1][j-1]+t,max(dp[i-1][j], dp[i][j-1]))
                    dp[i][j] = max(t,dp[i][j])
        # print(dp)
        return dp[-1][-1]


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)

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0 for j in range(len(nums2))] for i in range(len(nums1))]
        dp[0][0] = nums1[0] * nums2[0]
        for j in range(1, len(nums2)):
            dp[0][j] = max(dp[0][j-1], nums1[0] * nums2[j])
        for i in range(1, len(nums1)):
            dp[i][0] = max(dp[i - 1][0], nums1[i] * nums2[0])
        for i in range(1, len(nums1)):
            for j in range(1, len(nums2)):
                dp[i][j] = max(max(dp[i-1][j - 1], 0) + (nums1[i] * nums2[j]), dp[i-1][j], dp[i][j-1])
        
        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 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
    # BUG, BUG!
    #return max(recursion(i, j-1), recursion(i-1,j), recursion(i-1,j-1) + max(0, a[i]*b[j]))
    #return max(recursion(i, j-1), recursion(i-1,j), recursion(i-1, j-1, False) + a[i]*b[j])
    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)