LeetCode Entry

1458. Max Dot Product of Two Subsequences

8.10.2023 hard 2023 kotlin

Max product of two subsequences

1458. Max Dot Product of Two Subsequences hard blog post substack image.png

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 aproach is trivial, let’s modify it into bottom up.

  • use sentry dp size to avoid writing ifs

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]
    }