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;
}
}