aboutsummaryrefslogtreecommitdiff
path: root/max_dot_product.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_dot_product.py')
-rw-r--r--max_dot_product.py31
1 files changed, 31 insertions, 0 deletions
diff --git a/max_dot_product.py b/max_dot_product.py
new file mode 100644
index 0000000..f7e1803
--- /dev/null
+++ b/max_dot_product.py
@@ -0,0 +1,31 @@
+# 1458. Max Dot Product of Two Subsequences
+
+"""
+given two arrays 'nums1, 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.
+"""
+
+class Solution(object):
+ def maxDotProduct(self, nums1, nums2):
+ n, m = len(nums1), len(nums2)
+ dp = [[0] * (m) for in xrange(n)]
+ for i in xrange(n):
+ for j in xrange(m):
+ dp[i][j] = nums1[i] * nums2[j]
+ if i and j:
+ dp[i][j] += max(dp[i - 1][j - 1], 0)
+ if i:
+ dp[i][j] = max(dp[i][j], dp[i - 1][j])
+ if j:
+ dp[i][j] = max(dp[i][j], dp[i][j - 1])
+ return dp[-1][-1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxDotProduct([2,1,-2,5], [3,0,-6])) # expect: 18
+ print(obj.maxDotProduct([3,-2],[2,-6,7])) # expect: 21
+ print(obj.maxDotProduct([-1,-1],[1,1])) # expect: -1