<p>Given two arrays <code>nums1</code>&nbsp;and <code><font face="monospace">nums2</font></code><font face="monospace">.</font></p>

<p>Return the maximum dot product&nbsp;between&nbsp;<strong>non-empty</strong> subsequences of nums1 and nums2 with the same length.</p>

<p>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,&nbsp;<code>[2,3,5]</code>&nbsp;is a subsequence of&nbsp;<code>[1,2,3,4,5]</code>&nbsp;while <code>[1,5,3]</code>&nbsp;is not).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [2,1,-2,5], nums2 = [3,0,-6]
<strong>Output:</strong> 18
<strong>Explanation:</strong> Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,-2], nums2 = [2,-6,7]
<strong>Output:</strong> 21
<strong>Explanation:</strong> Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [-1,-1], nums2 = [1,1]
<strong>Output:</strong> -1
<strong>Explanation: </strong>Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 500</code></li>
	<li><code>-1000 &lt;= nums1[i], nums2[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        
        '''
        First, determine whether all the numbers in nums1 or nums2 are either all positive or all negative. 
        For instance, if all the numbers in nums1 are positive and all the numbers in nums2 are negative, 
        then the result is min(nums1) * max(nums2).        
        '''

        '''
        existPositive1,existNegative1 = False, False
        for x in nums1:
            if x > 0:
                existPositive1 = True
                if existNegative1:
                    break
            elif x < 0:
                existNegative1 = True
                if existPositive1:
                    break
        
        if not existPositive1 or not existNegative1:
            existPositive2,existNegative2 = False, False
            for x in nums2:
                if x > 0:
                    existPositive2 = True
                    if existNegative2:
                        break
                elif x < 0:
                    existNegative2 = True
                    if existPositive2:
                        break

            if not existPositive2 or not existNegative2:
                if existPositive1==False and existNegative2==False: # nums1 is all negative numbers and nums2 is all positive numbers
                    return min(nums2)*max(nums1)
                elif existNegative1==False and existPositive2==False: # nums1 is all positive numbers and nums2 is all negative numbers 
                    return min(nums1)*max(nums2)
        '''
        '''
        Next, consider the scenario where both nums1 and nums2 include a mix of positive and negative numbers.
        In this case, the maximum dot product will always be greater than zero.
        '''

        m = len(nums1)
        n = len(nums2)

        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]  
        dpx = [[0 for _ in range(n+1)] for _ in range(m+1)]
        '''
        dp[i][j] represents the maximum dot product between nums1[0:i+1] and nums2[0:j+1] including nums[i]*nums[j].
        dpx[i][j] represents the maximum dot product between nums1[0:i+1] and nums2[0:j+1] excluding nums[i]*nums[j].
        Note: An initial value of 0 suggests that the resulting value should be greater than zero. 
              If the result is exactly zero, it indicates that the actual value is negative. 
              This would occur when all the numbers in either nums1 or nums2 are all positive or all negative.
        '''
        for i in range(0,m):
            for j in range(0,n):
                dp[i][j] = max(dp[i-1][j-1],dpx[i-1][j-1]) + nums1[i]*nums2[j]
                dpx[i][j] = max(dp[i-1][j],dpx[i-1][j],dp[i][j-1],dpx[i][j-1])

        x = max(dp[m-1][n-1],dpx[m-1][n-1])
        if x > 0:
            return x
        else: # x==0 
            '''
            If x == 0, it implies that the result should be negative. 
            In this scenario, all the numbers in either nums1 or nums2 are all positive or all negative. 
            Therefore, we simply return the maximum value of dp[i][j] for all i and j.            
            '''
            maxV = -math.inf
            for i in range(m):
                for j in range(n):
                    maxV = max(maxV,dp[i][j])

            return maxV
25600