Max dot product of two subsequences

Array Dynamic Programming

69.3% acceptance

Feb 25, 2026

2151

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 array is a new array that is formed from the original array by deleting some of the elements (possibly none) without disturbing the relative positions of the remaining elements.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_dot_product(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let m = nums1.len();
    let n = nums2.len();
    let neg_inf = i32::MIN / 2;
    let mut dp = vec![vec![neg_inf; n + 1]; m + 1];
    for i in 1..=m {
      for j in 1..=n {
        let prod = nums1[i - 1] * nums2[j - 1];
        dp[i][j] = dp[i][j]
          .max(prod)
          .max(dp[i - 1][j - 1].max(0) + prod)
          .max(dp[i - 1][j])
          .max(dp[i][j - 1]);
      }
    }
    dp[m][n]
  }
}