LeetCode POTD 1458 – Maximum Dot Product of Two Subsequences

Описание: In this video, we solve LeetCode Problem 1458: Maximum Dot Product of Two Subsequences using Dynamic Programming (Tabulation).
📘 Problem Overview
🔹 You are given two integer arrays nums1 and nums2
🔹 You must choose non-empty subsequences from both arrays
🔹 Both subsequences must be of the same length
🔹 The goal is to maximize their dot product
📌 Dot Product =
(a1 × b1) + (a2 × b2) + ...
🚀 Approach Used (Dynamic Programming – Tabulation)
We use a bottom-up DP approach to explore all valid subsequences efficiently.
🔹 DP Definition
dp[i][j] = maximum dot product
using nums1[i…] and nums2[j…]
with at least one pair selected
🔹 Why We Use −∞ (Integer.MIN_VALUE)
🚫 Empty subsequences are not allowed
If we used 0, the algorithm could skip all elements and return 0
This would be incorrect when all valid dot products are negative
👉 Using minus infinity blocks invalid (empty) choices and forces at least one pair to be selected
🔹 DP Transition
At each (i, j) we have three choices:
1️⃣ Take both elements
nums1[i] × nums2[j] + max(0, dp[i+1][j+1])
2️⃣ Skip nums1[i]
dp[i+1][j]
3️⃣ Skip nums2[j]
dp[i][j+1]
We take the maximum of these.
🔹 Tabulation Order
The DP table is filled from bottom-right to top-left
Because dp[i][j] depends on:
dp[i+1][j]
dp[i][j+1]
dp[i+1][j+1]
⏱️ Time & Space Complexity
Time Complexity: O(n × m)
Space Complexity: O(n × m)

#LeetCode
#LeetCode1458
#DynamicProgramming
#DP
#Subsequence
#DSA
#CodingInterview
#FAANG
#Java