Problem

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

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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

Solution

Method 1 – Dynamic Programming (2D DP)

Intuition

We use a 2D DP table to track the maximum dot product for all pairs of prefixes of nums1 and nums2. At each step, we can either take both elements, skip one from nums1, or skip one from nums2. We must ensure at least one pair is chosen.

Approach

  1. Create a DP table dp[i][j] for the max dot product using first i elements of nums1 and first j elements of nums2.
  2. For each pair (i, j), consider:
    • Take both: nums1[i] * nums2[j] + max(0, dp[i-1][j-1])
    • Skip nums1[i]: dp[i-1][j]
    • Skip nums2[j]: dp[i][j-1]
  3. Initialize dp with a very small value to ensure at least one pair is chosen.
  4. The answer is dp[m-1][n-1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MIN));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int prod = nums1[i] * nums2[j];
                dp[i][j] = max({prod, (i > 0 && j > 0 ? max(0, dp[i-1][j-1]) + prod : prod),
                                (i > 0 ? dp[i-1][j] : INT_MIN),
                                (j > 0 ? dp[i][j-1] : INT_MIN)});
            }
        }
        return dp[m-1][n-1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func maxDotProduct(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = -1 << 30
        }
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            prod := nums1[i] * nums2[j]
            dp[i][j] = max(prod, prod+max(0, get(dp, i-1, j-1)), get(dp, i-1, j), get(dp, i, j-1))
        }
    }
    return dp[m-1][n-1]
}
func get(dp [][]int, i, j int) int {
    if i < 0 || j < 0 {
        return -1 << 30
    }
    return dp[i][j]
}
func max(a ...int) int {
    ans := a[0]
    for _, v := range a {
        if v > ans {
            ans = v
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i)
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int prod = nums1[i] * nums2[j];
                dp[i][j] = Math.max(prod, Math.max(prod + Math.max(0, (i > 0 && j > 0 ? dp[i-1][j-1] : 0)),
                    Math.max(i > 0 ? dp[i-1][j] : Integer.MIN_VALUE,
                             j > 0 ? dp[i][j-1] : Integer.MIN_VALUE)));
            }
        }
        return dp[m-1][n-1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun maxDotProduct(nums1: IntArray, nums2: IntArray): Int {
        val m = nums1.size
        val n = nums2.size
        val dp = Array(m) { IntArray(n) { Int.MIN_VALUE } }
        for (i in 0 until m) {
            for (j in 0 until n) {
                val prod = nums1[i] * nums2[j]
                dp[i][j] = maxOf(prod,
                    prod + maxOf(0, if (i > 0 && j > 0) dp[i-1][j-1] else 0),
                    if (i > 0) dp[i-1][j] else Int.MIN_VALUE,
                    if (j > 0) dp[i][j-1] else Int.MIN_VALUE)
            }
        }
        return dp[m-1][n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxDotProduct(self, nums1: list[int], nums2: list[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[float('-inf')] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                prod = nums1[i] * nums2[j]
                dp[i][j] = max(prod,
                    prod + max(0, dp[i-1][j-1] if i > 0 and j > 0 else 0),
                    dp[i-1][j] if i > 0 else float('-inf'),
                    dp[i][j-1] if j > 0 else float('-inf'))
        return dp[m-1][n-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_dot_product(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let m = nums1.len();
        let n = nums2.len();
        let mut dp = vec![vec![i32::MIN; n]; m];
        for i in 0..m {
            for j in 0..n {
                let prod = nums1[i] * nums2[j];
                dp[i][j] = prod.max(prod + dp.get(i.wrapping_sub(1)).and_then(|row| row.get(j.wrapping_sub(1))).copied().unwrap_or(0).max(0))
                    .max(dp.get(i.wrapping_sub(1)).and_then(|row| row.get(j)).copied().unwrap_or(i32::MIN))
                    .max(dp.get(i).and_then(|row| row.get(j.wrapping_sub(1))).copied().unwrap_or(i32::MIN));
            }
        }
        dp[m-1][n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maxDotProduct(nums1: number[], nums2: number[]): number {
        const m = nums1.length, n = nums2.length;
        const dp = Array.from({length: m}, () => Array(n).fill(-Infinity));
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                const prod = nums1[i] * nums2[j];
                dp[i][j] = Math.max(prod,
                    prod + Math.max(0, i > 0 && j > 0 ? dp[i-1][j-1] : 0),
                    i > 0 ? dp[i-1][j] : -Infinity,
                    j > 0 ? dp[i][j-1] : -Infinity);
            }
        }
        return dp[m-1][n-1];
    }
}

Complexity

  • ⏰ Time complexity: O(mn) — We fill a 2D DP table for all pairs.
  • 🧺 Space complexity: O(mn) — For the DP table.