Max Dot Product of Two Subsequences - Practice Coding Problems

Max Dot Product of Two Subsequences - Problem

Given two arrays nums1 and nums2, find the maximum dot product between non-empty subsequences of the same length.

The dot product of two sequences is the sum of products of corresponding elements. For example, the dot product of [2, 3] and [1, 4] is 2×1 + 3×4 = 14.

A subsequence is formed by deleting some (possibly zero) elements from the original array while maintaining the relative order. For instance, [2, 5] is a valid subsequence of [1, 2, 3, 5], but [5, 2] is not.

Goal: Return the maximum possible dot product between equal-length subsequences from both arrays.

Input & Output

example_1.py — Basic Case

$ Input: nums1 = [2,1,-2,5], nums2 = [3,0,-1]

› Output: 15

💡 Note: Take subsequence [5] from nums1 and [3] from nums2. Dot product = 5 × 3 = 15, which is the maximum possible.

example_2.py — Multiple Elements

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

› Output: 21

💡 Note: Take subsequence [3,-2] from nums1 and [2,7] from nums2 (skipping -6). Dot product = 3×2 + (-2)×7 = 6 - 14 = -8. Wait, better choice: take [3] and [7] for 3×7 = 21.

example_3.py — All Negative

$ Input: nums1 = [-1,-1], nums2 = [-1,-1]

› Output: 1

💡 Note: When all numbers are negative, the best strategy is to take the single largest (least negative) element from each array: (-1) × (-1) = 1.

Constraints

1 ≤ nums1.length, nums2.length ≤ 500
-1000 ≤ nums1[i], nums2[i] ≤ 1000
Both subsequences must be non-empty
Subsequences must have the same length

Visualization

Tap to expand

Understanding the Visualization

Evaluate Each Position

At each stock pair, decide: buy both, skip first period, or skip second period

Calculate Profit

If buying both stocks, multiply their values (dot product)

Explore All Combinations

Use memoization to efficiently try all valid portfolio combinations

Find Maximum

Return the portfolio combination with the highest total value

Key Takeaway

🎯 Key Insight: Use dynamic programming to systematically explore all portfolio combinations while avoiding redundant calculations through memoization, achieving optimal O(m×n) performance.

Asked in

G Google 28 a Amazon 22 ⊞ Microsoft 18 Apple 15

The optimal approach uses dynamic programming with memoization to efficiently explore all possible subsequence combinations. At each position (i,j), we have three choices: take both elements (adding their product), skip the first element, or skip the second element. The key insight is that we can build the optimal solution incrementally while avoiding redundant calculations through memoization, achieving O(m×n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming (Optimal)	O(m × n)	O(m × n)	Build optimal solution incrementally using memoization
Brute Force (Generate All Subsequences)	O(2^(m+n) × min(m,n))	O(2^(m+n))	Generate all possible subsequences and compute dot products

Dynamic Programming (Optimal) — Algorithm Steps

Define dp(i, j) as maximum dot product using elements from nums1[i:] and nums2[j:]
Base case: if we've processed all elements, return negative infinity
For each position, try three options: take both elements, skip first, skip second
Use memoization to avoid recalculating subproblems
Return the maximum value among all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Start from position (0,0) in both arrays

Three Choices

At each step: take both, skip first, or skip second

Memoization

Store results to avoid recalculating subproblems

Optimal Solution

Return maximum value from all explored paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

#define MAX_MEMO 10000

typedef struct {
    int i, j;
    int value;
} MemoEntry;

MemoEntry memo[MAX_MEMO];
int memoSize = 0;

int findMemo(int i, int j) {
    for (int k = 0; k < memoSize; k++) {
        if (memo[k].i == i && memo[k].j == j) {
            return memo[k].value;
        }
    }
    return INT_MIN - 1; // Not found
}

void addMemo(int i, int j, int value) {
    if (memoSize < MAX_MEMO) {
        memo[memoSize].i = i;
        memo[memoSize].j = j;
        memo[memoSize].value = value;
        memoSize++;
    }
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int dp(int* nums1, int nums1Size, int* nums2, int nums2Size, int i, int j) {
    if (i >= nums1Size || j >= nums2Size) {
        return INT_MIN;
    }
    
    int cached = findMemo(i, j);
    if (cached != INT_MIN - 1) {
        return cached;
    }
    
    // Option 1: Take both current elements
    int takeBoth = nums1[i] * nums2[j];
    
    // Try to extend with remaining elements
    int remaining = dp(nums1, nums1Size, nums2, nums2Size, i + 1, j + 1);
    if (remaining != INT_MIN) {
        takeBoth += remaining;
    }
    
    // Option 2: Skip nums1[i]
    int skipFirst = dp(nums1, nums1Size, nums2, nums2Size, i + 1, j);
    
    // Option 3: Skip nums2[j]
    int skipSecond = dp(nums1, nums1Size, nums2, nums2Size, i, j + 1);
    
    int result = max(takeBoth, max(skipFirst, skipSecond));
    addMemo(i, j, result);
    return result;
}

int maxDotProduct(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    memoSize = 0;
    return dp(nums1, nums1Size, nums2, nums2Size, 0, 0);
}

int main() {
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

We solve each subproblem (i,j) exactly once, and there are m×n subproblems

✓ Linear Growth

Space Complexity

O(m × n)

Memoization table stores results for each (i,j) pair

⚡ Linearithmic Space

29.1K Views

Medium Frequency

~25 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler