1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
|