LeetCode #1458.Max Dot Product of Two Subsequences

Source: Dev.to

Problem

Given two arrays nums1 and nums2, return the maximum dot product between non‑empty subsequences of nums1 and nums2 that have the same length.

A subsequence of an array is a new array formed by deleting some (or none) of the elements without disturbing the relative order of the remaining elements.
For example, [2,3,5] is a subsequence of [1,2,3,4,5], while [1,5,3] is not.

Example 1

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2. Their dot product is 2*3 + (-2)*(-6) = 18.

Example 2

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2. Their dot product is 3*7 = 21.

Example 3

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2. Their dot product is -1.

Constraints

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

Discussion

The problem can be approached with dynamic programming, similar to the Longest Common Subsequence (LCS) technique.
We maintain a 2‑D DP array where dp[i][j] stores the maximum dot product using prefixes nums1[0..i] and nums2[0..j].
For each pair (i, j) we consider:

1. Extending the previous best subsequence by multiplying nums1[i] * nums2[j].
2. Starting a new subsequence with just nums1[i] * nums2[j].
3. Skipping nums1[i] (use dp[i‑1][j]).
4. Skipping nums2[j] (use dp[i][j‑1]).

Edge cases for the first row and first column are handled separately to ensure non‑empty subsequences.

Solution

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int firstRowMax = nums1[0] * nums2[0];
        dp[0][0] = firstRowMax;

        // Initialize first row
        for (int j = 1; j < nums2.length; j++) {
            int current = nums1[0] * nums2[j];
            firstRowMax = Math.max(firstRowMax, current);
            dp[0][j] = firstRowMax;
        }

        int answer = firstRowMax;

        // Fill the DP table
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int current = nums1[i] * nums2[j];
                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], current);
                } else {
                    dp[i][j] = Math.max(
                        dp[i - 1][j - 1] + current,
                        Math.max(
                            current,
                            Math.max(dp[i - 1][j], dp[i][j - 1])
                        )
                    );
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        return answer;
    }
}