RUST GYM Leetcode 1458 Max Dot Product of Two Subsequences Rust Solution

1458. Max Dot Product of Two Subsequences

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

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.

Constraints:

1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

Rust Solution

struct Solution;

impl Solution {
    fn max_dot_product(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let m = nums2.len();
        let mut memo = vec![vec![std::i32::MIN; m + 1]; n + 1];
        Self::dp(n, m, &mut memo, &nums1, &nums2)
    }
    fn dp(n: usize, m: usize, memo: &mut Vec<Vec<i32>>, nums1: &[i32], nums2: &[i32]) -> i32 {
        if memo[n][m] > std::i32::MIN {
            memo[n][m]
        } else {
            let mut res = nums1[n - 1] * nums2[m - 1];
            if n > 1 && m > 1 {
                res = res.max(Self::dp(n - 1, m - 1, memo, nums1, nums2).max(0) + res);
            }
            if n > 1 {
                res = res.max(Self::dp(n - 1, m, memo, nums1, nums2));
            }
            if m > 1 {
                res = res.max(Self::dp(n, m - 1, memo, nums1, nums2));
            }
            memo[n][m] = res;
            res
        }
    }
}

#[test]
fn test() {
    let nums1 = vec![2, 1, -2, 5];
    let nums2 = vec![3, 0, -6];
    let res = 18;
    assert_eq!(Solution::max_dot_product(nums1, nums2), res);
    let nums1 = vec![3, -2];
    let nums2 = vec![2, -6, 7];
    let res = 21;
    assert_eq!(Solution::max_dot_product(nums1, nums2), res);
    let nums1 = vec![-1, -1];
    let nums2 = vec![1, 1];
    let res = -1;
    assert_eq!(Solution::max_dot_product(nums1, nums2), res);
}

Having problems with this solution? Click here to submit an issue on github.