DEV Community

Hector Williams
Hector Williams

Posted on

LeetCode #1458.Max Dot Product of Two Subsequences

Many engineers find leetcode problems hard and not a reflection of the actual work to do. I do have some sympathy for this view. Nonetheless, I do think that these questions can help practice and build programming skills. Due to this and the fact that these prop up in interviews, I will post discussions of these from time to time.Follow me on twitter,github or Linkedin for these and more.

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 an 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

Discussion

I was stumped by this question. I read the hints and somebody mentioned that it was similar to Longest Common Subsequence. That got me thinking. I had to use a 2-D dp array to get the result.

I also had to keep track of the multiplication of each number from each array along with the values from the previous row,current column and the previous column and current row.For edge cases I had to calculate the values for the first row and the first column.I came up with the solution below which passed all 70 cases.

Solution

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
     int  [] [] dp=new int[nums1.length] [nums2.length];   
     int firstRowMax=nums1[0]*nums2[0];
     int answer=0;
     dp[0][0]=firstRowMax;
     for(int j=1;j<nums2.length;j++){
      int current=nums1[0]*nums2[j];
      firstRowMax=Math.max(firstRowMax,current);
      dp[0][j]=firstRowMax;
     }
     answer=firstRowMax;
     for(int i=1;i<nums1.length;i++){
      for(int j=0;j<nums2.length;j++){
        int current=nums1[i]*nums2[j];
        if(j==0) dp[i][j]=Math.max(dp[i-1][j],current);   
        else
         dp[i][j]=Math.max(dp[i-1][j-1]+current,Math.max(current,Math.max(dp[i-1][j],dp[i][j-1])));
        answer=Math.max(answer,dp[i][j]);
      }  
     }
     return answer;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)