8.10.2023
1458. Max Dot Product of Two Subsequences hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/363
Problem TLDR
Max product of two subsequences
Intuition
We can search in all possible subsequences in O(n^2) by choosing between: take element and stop, take and continue, skip first, skip second.
Approach
The top-down approach is trivial, let’s modify it into bottom up.
use sentry
dp
size to avoid writingif
s
Complexity
Time complexity:
O(n^2)Space complexity:
O(n^2)
Code
fun maxDotProduct(nums1: IntArray, nums2: IntArray): Int {
val dp = Array(nums1.size + 1) { Array(nums2.size + 1) { -1000000 } }
for (j in nums2.lastIndex downTo 0)
for (i in nums1.lastIndex downTo 0)
dp[i][j] = maxOf(
nums1[i] * nums2[j],
nums1[i] * nums2[j] + dp[i + 1][j + 1],
dp[i][j + 1],
dp[i + 1][j])
return dp[0][0]
}