https://leetcode.com/problems/max-dot-product-of-two-subsequences

Let dp[i][j] be the maximum dot product for first i numbers from nums1 and first j numbers from nums2. Note, that dp[0][0] = 0 is for the case where we take 0 elements from both nums1 and nums2 (that is we use dummy first column and row). Let us forgot for the moment, that product need to be not empty, then we can just use dp[i+1][j+1] = max(dp[i][j] + nums1[i]*nums2[j], dp[i][j+1], dp[i+1][j]), because we can:

  1. Either include nums1[i]*nums2[j] into our dot product and we need to add value of dp[i][j]
  2. Or do not inculde nums1[i]*nums2[j], that is choose the best from dp[i][j+1] or dp[i+1][j] problems.

Now, if we do it it can happen that our product is empty, and we need to handle this case separatly: it can happen if all numbers in one array are negative and all numbers in another array is positive.

class Solution:
    def maxDotProduct(self, nums1, nums2):
        M, N = len(nums1), 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 _ in range(N+1)] for _ in range(M+1)]
        for i in range(M):
            for j in range(N):
                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]

If you like the solution, you can upvote it on leetcode discussion section: Problem 1458