LeetCode 1458: Max Dot Product of Two Subsequences Solution

Master LeetCode problem 1458 (Max Dot Product of Two Subsequences), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1458. Max Dot Product of Two Subsequences

Hard

Array Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming to compute the maximum dot product of two subsequences of nums1 and nums2 with the same length. We will create a 2D DP array to store the maximum dot product at each index of the two arrays. The recurrence relation for calculating the maximum dot product at index (i, j) can be defined as follows:

dp[i][j] = max(nums1[i] * nums2[j], nums1[i] * nums2[j] + max(0, dp[i-1][j-1]))

We can initialize the DP array with zeros and then iterate over each pair of indices in nums1 and nums2, updating the DP array based on the recurrence relation. The final answer will be the maximum value in the DP array.

The time complexity of this approach is O(n1 * n2) where n1 and n2 are the lengths of nums1 and nums2 respectively. The space complexity is also O(n1 * n2) for the DP array.

Solution Code

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int[][] dp = new int[n1][n2];
        
        dp[0][0] = nums1[0] * nums2[0];
        
        for (int i = 1; i < n1; i++) {
            dp[i][0] = Math.max(nums1[i] * nums2[0], nums1[i] * nums2[0] + dp[i-1][0]);
        }
        
        for (int j = 1; j < n2; j++) {
            dp[0][j] = Math.max(nums1[0] * nums2[j], nums1[0] * nums2[j] + dp[0][j-1]);
        }
        
        for (int i = 1; i < n1; i++) {
            for (int j = 1; j < n2; j++) {
                dp[i][j] = Math.max(nums1[i] * nums2[j], nums1[i] * nums2[j] + Math.max(0, dp[i-1][j-1]));
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
                dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
            }
        }
        
        return dp[n1-1][n2-1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1458 (Max Dot Product of Two Subsequences)?

This page provides optimized solutions for LeetCode problem 1458 (Max Dot Product of Two Subsequences) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1458 (Max Dot Product of Two Subsequences)?

The time complexity for LeetCode 1458 (Max Dot Product of Two Subsequences) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1458 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1458 in Java, C++, or Python.

Back to LeetCode Solutions