Given two arrays nums1&nbsp;and nums2.

Return the maximum dot product&nbsp;between&nbsp;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,&nbsp;[2,3,5]&nbsp;is a subsequence of&nbsp;[1,2,3,4,5]&nbsp;while [1,5,3]&nbsp;is not).

&nbsp;
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.

&nbsp;
Constraints:


	1 &lt;= nums1.length, nums2.length &lt;= 500
	-1000 &lt;= nums1[i], nums2[i] &lt;= 1000


class Solution:
    def maxDotProduct(self, A, B):
        dp = [float('-inf')] * (len(B)+1)
        for i in range(len(A)):
            prev = float('-inf')
            for j in range(len(B)):
                product = A[i] * B[j]
                prev, dp[j+1] = dp[j+1], max(dp[j+1], dp[j], product, prev + product)
        return dp[-1]
class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int N = nums1.length, M = nums2.length;
        int[][] dp = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j] = nums1[i] * nums2[j];
                if (i > 0 && j > 0 && dp[i - 1][j - 1] > 0) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                if (i > 0 && dp[i - 1][j] > dp[i][j]) {
                    dp[i][j] = dp[i - 1][j];
                }
                if (j > 0 && dp[i][j - 1] > dp[i][j]) {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[N - 1][M - 1];
    }
}
class Solution
{
    public:

        const int NEG_INF = -10e8;
        int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {

        int n = nums1.size();
        int m = nums2.size();

        // NOTE : we can't initialize with INT_MIN because adding any val with it will give overflow
        // that is why we prefer 10^7 or 10^8

        vector<vector<int>> dp(n+1, vector<int>(m+1, NEG_INF));

        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {

                int temp_p = nums1[i-1]*nums2[j-1];

        // Although it is a variation of LCS but here we need to check for all answers we already know in dp
        // Why only temp_p ? -> suppose in dp[i-1][j-1] is -10^7 + temp_p is 2 == gives nearly -10^7(which is wrong ans)
        // For Remaining comparisons we already know why !

                dp[i][j] = max({ dp[i-1][j-1] + temp_p,
                                      temp_p,
                                      dp[i-1][j],
                                      dp[i][j-1]
                              });
            }
        }

        return dp[n][m];
    }
};
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDotProduct = function(nums1, nums2) {
    var m = nums1.length;
    var n = nums2.length;
    if (!m || !n) return 0;
    var dp = [[nums1[0] * nums2[0]]];
    for (var i = 1; i < m; i++) {
        dp[i] = [];
        dp[i][0] = Math.max(nums1[i] * nums2[0], dp[i-1][0]);
    }
    for (var i = 1; i < n; i++) dp[0][i] = Math.max(nums1[0] * nums2[i], dp[0][i-1]);
    for (var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            var val = nums1[i] * nums2[j];
            dp[i][j] = Math.max(val, val + dp[i-1][j-1], dp[i][j-1], dp[i-1][j]);
        }
    }
    return dp[m - 1][n - 1];
};
Max Dot Product of Two Subsequences