Re: [閒聊] 每日leetcode
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]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1767884649.A.7E5.html
討論串 (同標題文章)
完整討論串 (本文為第 1562 之 1563 篇)：