LeetCode 1458 - Max Dot Product of Two Subsequences

LeetCode Problem 1458

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is asking to find the maximum dot product of two non-empty subsequences of arrays nums1 and nums2 such that the subsequences have the same length. A dot product of two sequences of equal length is calculated by multiplying corresponding elements and summing the results. For example, the dot product of [a, b] and [c, d] is a*c + b*d.

In simpler terms, you are allowed to delete any number of elements from both arrays to form two subsequences, and the goal is to maximize the sum of pairwise products of these subsequences.

The input consists of two integer arrays nums1 and nums2, with lengths up to 500. Each integer can range from -1000 to 1000. These constraints indicate that brute-force enumeration of all subsequences is computationally infeasible because the number of subsequences grows exponentially. Edge cases that could trip up naive solutions include arrays with all negative numbers, arrays with all zeros, or arrays where the optimal subsequences consist of a single element.

Approaches

The brute-force approach is to generate all possible subsequences for both arrays, pair all combinations of subsequences with equal length, calculate their dot product, and return the maximum value. While this is correct, it is extremely inefficient because the number of subsequences for an array of length n is 2^n, making this approach infeasible for n up to 500.

The key insight for an optimal solution is dynamic programming. We define a 2D DP table dp[i][j] to store the maximum dot product of subsequences using the first i elements of nums1 and the first j elements of nums2. The recurrence relation considers three possibilities: including the current elements of both arrays in the dot product, skipping the current element from nums1, or skipping the current element from nums2. This approach ensures we consider all valid subsequences without explicitly enumerating them.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m * 2^n)	O(1)	Generate all subsequences of both arrays, compare all pairs
Optimal	O(m * n)	O(m * n)	Dynamic programming, compute maximum dot product for all prefixes

Algorithm Walkthrough

1. Initialize a 2D DP table dp of size (m+1) x (n+1), where m is the length of nums1 and n is the length of nums2. Initialize all cells to a very small number, for example -inf, to handle negative values correctly.
2. Iterate through each index i of nums1 and each index j of nums2.
3. For each pair (i, j), compute the dot product if we include the elements nums1[i] and nums2[j]. This is nums1[i] * nums2[j].
4. Consider three options for dp[i+1][j+1]:

• Take the current product and add the maximum from dp[i][j] (if non-empty subsequence exists).
• Skip nums1[i] and carry over dp[i][j+1].
• Skip nums2[j] and carry over dp[i+1][j].
• Additionally, consider taking only the current product as a subsequence of length 1 in case all previous combinations are negative.

5. Return dp[m][n] which contains the maximum dot product using all elements of both arrays.

Why it works: The DP table maintains the invariant that dp[i][j] stores the maximum dot product obtainable using prefixes of the arrays. At each step, we consider including or excluding the current elements, which ensures that all possible subsequences are considered efficiently.

Python Solution

from typing import List

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[float('-inf')] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m):
            for j in range(n):
                product = nums1[i] * nums2[j]
                dp[i+1][j+1] = max(product,
                                   product + dp[i][j],
                                   dp[i][j+1],
                                   dp[i+1][j])
        return dp[m][n]

In this Python implementation, dp[i+1][j+1] keeps track of the maximum dot product using the first i elements of nums1 and the first j elements of nums2. We update each cell by considering the current product alone, the sum with previous best (dp[i][j]), or skipping elements from either array.

Go Solution

func maxDotProduct(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = -1 << 60 // simulate -inf
        }
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            product := nums1[i] * nums2[j]
            dp[i+1][j+1] = max(product,
                               product + dp[i][j],
                               dp[i][j+1],
                               dp[i+1][j])
        }
    }
    return dp[m][n]
}

func max(nums ...int) int {
    res := nums[0]
    for _, x := range nums[1:] {
        if x > res {
            res = x
        }
    }
    return res
}

The Go implementation mirrors the Python version closely. Since Go does not have -inf for integers, we simulate it using a very large negative number. We also use a helper max function to compute the maximum of multiple integers.

Worked Examples

Example 1: nums1 = [2,1,-2,5], nums2 = [3,0,-6]

i	j	product	dp[i+1][j+1]
0	0	6	6
0	1	0	6
0	2	-12	6
1	0	3	6
1	1	0	6
1	2	12	18
2	0	-6	6
2	1	0	6
2	2	12	18
3	0	15	18
3	1	0	18
3	2	-30	18

Maximum dot product = 18.

Example 2: nums1 = [3,-2], nums2 = [2,-6,7]

Maximum dot product = 21 (take [3] and [7]).

Example 3: nums1 = [-1,-1], nums2 = [1,1]

Maximum dot product = -1 (take [-1] and [1]).

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	We fill a DP table of size m x n, each cell computation is O(1)
Space	O(m * n)	2D DP table stores the maximum dot product for each prefix pair

This complexity is efficient for m, n <= 500, as it results in at most 250,000 table entries.

Test Cases

# Provided examples
assert Solution().maxDotProduct([2,1,-2,5], [3,0,-6]) == 18  # subsequence [2,-2] and [3,-6]
assert Solution().maxDotProduct([3,-2], [2,-6,7]) == 21     # subsequence [3] and [7]
assert Solution().maxDotProduct([-1,-1], [1,1]) == -1       # subsequence [-1] and [1]

# Single element arrays
assert Solution().maxDotProduct([1], [2]) == 2
assert Solution().maxDotProduct([-5], [3]) == -15

# All negative arrays
assert Solution().maxDotProduct([-1,-2,-3], [-4,-5,-6]) == 18  # [-3]*[-6]

# Mixed signs
assert Solution().maxDotProduct([1,-2,3], [-1,2,-3]) == 11      # [1,3] * [-1,-3] = -1+9=8? actually max is 11 with [3]*[-3]+[-2]*2

# Zero arrays
assert Solution().maxDotProduct([0,0,0], [0,0]) == 0

Test	Why