Max Dot Product with 0 Insertions

Problem Overview

Align array b fully with a subsequence of a in order — skipping an element of a is equivalent to inserting a 0 there (adds nothing to the dot product).

Intuition

Align array b fully with a subsequence of a in order — skipping an element of a is equivalent to inserting a 0 there (adds nothing to the dot product). Maximize sum of paired products a[i_k] * b[k]. Use DP on indices (i, j): how to best match b[j..] using a[i..].

Algorithm

1dp(i, j): max dot product for suffixes starting at i in a and j in b.
2If j == m: return 0 (all of b matched). If too few elements left in a: invalid.
3skip = dp(i + 1, j) — drop a[i] (zero insertion).
4match = a[i] * b[j] + dp(i + 1, j + 1) when the suffix is feasible.
5Return max(skip, match); memoize on (i, j).

Example Walkthrough

Input: a = [2, 1, 3], b = [1, 2]

1. Pair a[0]=2 with b[0]=1, skip a[1], pair a[2]=3 with b[1]=2 → 2 + 6 = 8.
2. Or skip a[0], match 1*1 and 3*2 = 7.

Output: 8

Common Pitfalls

• Require n - i >= m - j — every remaining b element needs a distinct match in a.
• Use Integer.MIN_VALUE for impossible states; only add dp(i+1,j+1) when not invalid.
• Same spirit as LC 1458 but b must be fully consumed (zeros only on a side).

Max Dot Product with 0 Insertions.java

Java

// Approach: Match all of b in order using a subsequence of a (skipping a[i] = inserting 0 on a's side).
// dp[i][j] = max dot product pairing b[j..] with a[i..]. Skip a[i] or take a[i]*b[j] and advance both.
// Time: O(n * m) Space: O(n * m)

import java.util.*;

class Solution {

    int[][] dp;

    public int maxDotProduct(int[] a, int[] b) {
        int n = a.length;
        int m = b.length;

        dp = new int[n][m];

        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        return solve(a, b, 0, 0);
    }

    private int solve(int[] a, int[] b, int i, int j) {

        int n = a.length;
        int m = b.length;

        // All elements of b have been matched
        if (j == m) {
            return 0;
        }

        // No elements left in a
        if (i == n) {
            return Integer.MIN_VALUE;
        }

        // Not enough elements left in a
        if (n - i < m - j) {
            return Integer.MIN_VALUE;
        }

        if (dp[i][j] != -1) {
            return dp[i][j];
        }

        // Skip current element of a
        int skip = solve(a, b, i + 1, j);

        // Match current elements
        int match = a[i] * b[j];
        int next = solve(a, b, i + 1, j + 1);

        if (next != Integer.MIN_VALUE) {
            match += next;
        }

        return dp[i][j] = Math.max(skip, match);
    }
}

Was this solution helpful?