Max Dot Product Of Two Subsequences - Leetcode Solution

Problem: Max Dot Product Of Two Subsequences (https://leetcode.com/problems/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).

Solution:

Approach: Dynamic Programming

We can solve this problem using dynamic programming.

Let dp[i][j] be the maximum dot product of two subsequences of nums1[0...i-1] and nums2[0...j-1].

For each i in nums1 and j in nums2, we can either include or exclude the ith element of nums1 and the jth element of nums2.

1. If we exclude ith element of nums1 and jth element of nums2:

Then the maximum dot product will be dp[i-1][j-1] if dp[i-1][j-1] is positive. Otherwise, we should exclude both the ith element of nums1 and jth element of nums2. In this case, the maximum dot product will be 0.

2. If we include ith element of nums1 and jth element of nums2:

Then the maximum dot product will be dp[i-1][j-1] + (nums1[i-1] * nums2[j-1]).

We can choose the maximum between the above two cases. Hence, the recursive formula for the dp array becomes:

dp[i][j] = max(dp[i-1][j-1], nums1[i-1]*nums2[j-1] + max(dp[i-1][j], dp[i][j-1]))

We need to find the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length. Hence, we need to find the maximum dot product between two subsequences of the same length for each i in nums1 and j in nums2.

The final answer will be the maximum value in the dp array.

Code:

int maxDotProduct(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(), m = nums2.size(); vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MIN));

    int maxDotProduct = INT_MIN;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            // Excluding ith element of nums1 and jth element of nums2
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
            
            // Including ith element of nums1 and jth element of nums2
            int dpIncluding = nums1[i-1]*nums2[j-1];
            // If dp[i-1][j-1] is positive, then add dp[i-1][j-1] to dpIncluding
            if(dp[i-1][j-1] > 0){
                dpIncluding += dp[i-1][j-1];
            }
            dp[i][j] = max(dp[i][j], dpIncluding);
            
            // Updating the maximum value in the dp array
            if(i == n && j == m){
                maxDotProduct = dp[i][j];
            }
        }
    }
    
    return maxDotProduct;
}

1