Dynamic Programming problems often look difficult at first because we need to make the best decision at every step. This problem is a perfect example. Although it talks about inserting zeros into an array, the actual problem is much simpler once we understand what those zero insertions really mean.
Let's understand the problem from scratch and gradually build the optimal solution.
Problem Statement
We are given two arrays:
We are allowed to insert zeros anywhere in array b until its size becomes equal to n.
After both arrays have equal length, we calculate their dot product.
a[0] * b[0] + a[1] * b[1] + ... + a[n-1] * b[n-1]
Our goal is to maximize this dot product.
Example
a = [2, 3, 1, 7, 8]
b = [3, 6, 7]
One possible arrangement is:
b = [0, 3, 0, 6, 7]
The dot product becomes:
2×0 + 3×3 + 1×0 + 7×6 + 8×7
= 0 + 9 + 0 + 42 + 56
= 107
This is the maximum possible answer.
Understanding What Zero Insertions Mean
Instead of thinking about inserting zeros, think about selecting positions in array a.
Suppose:
a = [2, 3, 1, 7, 8]
b = [3, 6, 7]
Since b has only three elements, we only need to choose three positions in a.
For example, choose the positions:
3
7
8
Then they are matched as follows:
3 → 3
7 → 6
8 → 7
Every other position automatically gets zero.
So the real problem becomes:
Choose exactly m positions from array a while preserving order so that the dot product is maximum.
This observation converts the problem into Dynamic Programming.
Why Greedy Does Not Work
Suppose:
a = [10, 1, 9]
b = [5, 6]
If we greedily match the largest values first:
10 × 6
9 × 5
This is not possible because the order of array b cannot change.
The sequence inside b must always remain:
5
then
6
So we need an approach that considers both possibilities at every step.
Dynamic Programming naturally handles this.
Thinking About Every Position
Suppose we are currently looking at:
a[i]
There are only two choices.
Choice 1: Skip This Element
Skip this element by inserting a zero at this position.
a[i]
0
Choice 2: Use This Element
Match it with the current element of array b.
a[i]
×
b[j]
Every position has only these two choices.
This observation directly leads to the DP recurrence.
Defining the DP State
Let:
dp[i][j]
represent the maximum dot product using:
For example:
dp[5][3]
means:
This is exactly our final answer.
The Two Choices
Suppose we are computing:
dp[i][j]
Choice 1: Skip Current Element
Do not match:
a[i-1]
Instead, insert a zero.
The answer remains:
dp[i-1][j]
Choice 2: Match Current Element
Match:
a[i-1]
with:
b[j-1]
Current contribution:
a[i-1] × b[j-1]
Plus the best answer using previous elements:
dp[i-1][j-1]
Therefore:
dp[i-1][j-1] + a[i-1] × b[j-1]
Finally:
dp[i][j]
=
max(
dp[i-1][j],
dp[i-1][j-1] + a[i-1] × b[j-1]
)
This is the complete Dynamic Programming solution.
DP Initialization
If we have no elements from b:
j = 0
then:
dp[i][0] = 0
because multiplying with all zeros gives zero.
If we have no elements from a:
i = 0
but still need to match some elements from b, this is impossible.
So:
dp[0][j] = Negative Infinity
This prevents invalid transitions.
DP Table Walkthrough
Consider:
a = [2,3,1,7,8]
b = [3,6,7]
Initially:
0 3 6 7
------------------
0 | 0 -∞ -∞ -∞
2 | 0
3 | 0
1 | 0
7 | 0
8 | 0
Now compute the table row by row.
For:
a = 2
dp[1][1]
Skip = 0
Take = 2 × 3 = 6
Answer = 6
Continue similarly.
Eventually:
dp[5][3]
becomes:
107
which is the final answer.
Java Implementation
class Solution {
public int maxDotProduct(int[] a, int[] b) {
int n = a.length;
int m = b.length;
int NEG = Integer.MIN_VALUE / 2;
int[][] dp = new int[n + 1][m + 1];
for (int j = 1; j <= m; j++) {
dp[0][j] = NEG;
}
for (int i = 1; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, m); j++) {
int skip = dp[i - 1][j];
int take = dp[i - 1][j - 1]
+ a[i - 1] * b[j - 1];
dp[i][j] = Math.max(skip, take);
}
}
return dp[n][m];
}
}
Dry Run
a = [1,2,3]
b = [4]
Initially:
dp[0][1] = -∞
Now:
For 1:
Take = 4
Skip = -∞
Answer = 4
For 2:
Take = 8
Skip = 4
Answer = 8
For 3:
Take = 12
Skip = 8
Answer = 12
Final answer:
12
which corresponds to:
b = [0,0,4]
Time Complexity
O(n × m)
Every DP state is computed exactly once.
Space Complexity
O(n × m)
for storing the DP table.
Key Takeaways
Inserting zeros is equivalent to skipping positions in array a.
The order of array b must always remain unchanged.
Every element of a has only two choices: skip it or match it.
These two choices naturally form the Dynamic Programming recurrence.
The solution runs efficiently in O(n × m) time, making it suitable for the given constraints.
Summary
The key insight is that inserting zeros into array b is equivalent to selectively matching elements from array a while preserving order. By modeling each position as either a "skip" or "match" decision, the problem naturally transforms into a Dynamic Programming solution with a simple recurrence. This approach efficiently computes the maximum possible dot product in O(n × m) time while maintaining the required ordering of both arrays.