1458. Max Dot Product of Two Subsequences
思路 :
类似最长共同子序列
所以用dp
把nums1的元素依序对nums2的元素进行相乘
dp[i][j]就会等于
1.dp[i-1][j]
2.dp[i][j-1]
3.dp[i-1][j-1] + nums1[i]*nums2[j]
这三个里面的最大值
接着把最后的值回传就好
然后要注意会有负值
所以用额外的一个数来记录单一nums1[i]*nums2[j]的最大值
如果dp[n][m]最后的值是0就回单一最大值
golang code
func maxDotProduct(nums1 []int, nums2 []int) int {
n, m := len(nums1), len(nums2)
maxSingleVal := math.MinInt64
dp1, dp2 := make([]int, m+1), make([]int, m+1)
for i := 0; i < n; i++ {
for j := 1; j <= m; j++ {
dotSum := nums1[i] * nums2[j-1]
maxSingleVal = max(maxSingleVal, dotSum)
dp2[j] = max(dp2[j-1], dp1[j], dotSum+dp1[j-1])
}
dp1, dp2 = dp2, dp1
dp2 = make([]int, m+1)
}
if dp1[m] == 0 {
return maxSingleVal
}
return dp1[m]
}