leetcode 1458
Published:
题目1458
给你两个数组 nums1 和 nums2 。
请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。
输入样例
输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6] 输出：18 解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。 它们的点积为 (2*3 + (-2)*(-6)) = 18 。
解析
子序列优先往DP靠，dp[i][j]代表nums1[i]，nums2[j]之前的最大值，状态转移方程如下： \(max[i][j] = max(f[i−1][j−1]+x_{ij},\ x_{ij},\ f[i−1][j],f[i][j−1],f[i−1][j−1])\)
题解
class Solution:
def maxDotProduct(self, nums1, nums2):
m=len(nums1)
n=len(nums2)
signal=[[0]*n for _ in range(m)]
signal[0][0]=nums1[0]*nums2[0]
for j in range(n):
for i in range(m):
cur,left,up=[nums1[i]*nums2[j]]*3
if i>0:
left=signal[i-1][j]
if j>0:
up=signal[i][j-1]
signal[i][j]=max(cur,up,left)
if i>0 and j>0:
lefup=signal[i-1][j-1]
signal[i][j]=max(signal[i][j],lefup+cur)
return signal[m-1][n-1]
def main():
numx=[2,1,-2,5]
numy=[3,0,-6]
solu=Solution()
print(solu.maxDotProduct(numx,numy))
if __name__ == '__main__':
main()