Maximum Multiplication Score — Problem & Solution
Maximum Multiplication Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Multiplication Score is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array a of length 4 and an array b of length at least 4.
Choose four indices i0 < i1 < i2 < i3 of b. Their score is a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]. Return the maximum score achievable.
CodeKairo bound: values lie in [-10^4, 10^4] (LeetCode allows ±10^5) so that the answer fits in a 32-bit integer.
Example 1
Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
Output: 26
Explanation: Indices 0, 1, 2, 5: 3·2 + 2·(-6) + 5·4 + 6·2.
Example 2
Input: a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
Output: -1
Explanation: Indices 0, 1, 3, 4.
Example 3
Input: a = [1,1,1,1], b = [1,2,3,4,5]
Output: 14
Constraints
a.length == 44 <= b.length <= 10^5-10^4 <= a[i], b[i] <= 10^4
Hints for Maximum Multiplication Score
Hint 1
Choose the four indices left to right: the only thing that matters about a partial choice is how many of
ait has used.Hint 2
Let
dp[k]be the best score after assigninga[0..k]to indices chosen among the elements scanned so far.Hint 3
For each
b[j], updatek = 3, 2, 1, 0(downwards):dp[k] = max(dp[k], dp[k-1] + a[k] * b[j]), withdp[-1] = 0.
How to solve Maximum Multiplication Score
A tiny knapsack over the four slots of a. Scanning b left to right, each element may fill the next slot after any partial assignment made strictly earlier, which keeps the indices increasing.
Approach
- Initialise
dp[0..3] = -∞. - For each
xinb, forkfrom 3 down to 0:prev = (k == 0 ? 0 : dp[k-1]); ifprevis finite,dp[k] = max(dp[k], prev + a[k] · x). - Return
dp[3].
Why it works
After scanning a prefix of b, dp[k] is the best way to place a[0..k] on increasing indices inside that prefix. A new element either is not used, or becomes the index of a[k] after an optimal placement of a[0..k-1] on earlier elements. Updating k downwards guarantees dp[k-1] still refers to strictly earlier elements.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Updating
kupwards lets one element fill two slots. - Scores can be negative — start from -∞, not 0.
- A greedy pick of the largest products ignores the index order.
Reference solution
Python
from typing import List
def maxScore(a: List[int], b: List[int]) -> int:
NEG = -10**18
dp = [NEG] * 4
for x in b:
for k in range(3, -1, -1):
prev = 0 if k == 0 else dp[k - 1]
if prev != NEG and prev + a[k] * x > dp[k]:
dp[k] = prev + a[k] * x
return dp[3]Java
public static int maxScore(int[] a, int[] b) {
final long NEG = Long.MIN_VALUE;
long[] dp = {NEG, NEG, NEG, NEG};
for (int x : b) {
for (int k = 3; k >= 0; k--) {
long prev = k == 0 ? 0 : dp[k - 1];
if (prev == NEG) continue;
long cand = prev + (long) a[k] * x;
if (cand > dp[k]) dp[k] = cand;
}
}
return (int) dp[3];
}C++
int maxScore(vector<int>& a, vector<int>& b) {
const long long NEG = LLONG_MIN;
long long dp[4] = {NEG, NEG, NEG, NEG};
for (int x : b) {
for (int k = 3; k >= 0; k--) {
long long prev = k == 0 ? 0 : dp[k - 1];
if (prev == NEG) continue;
long long cand = prev + (long long) a[k] * x;
if (cand > dp[k]) dp[k] = cand;
}
}
return (int) dp[3];
}JavaScript
var maxScore = function(a, b) {
var dp = [-Infinity, -Infinity, -Infinity, -Infinity];
for (var j = 0; j < b.length; j++) {
for (var k = 3; k >= 0; k--) {
var prev = k === 0 ? 0 : dp[k - 1];
if (prev !== -Infinity && prev + a[k] * b[j] > dp[k]) dp[k] = prev + a[k] * b[j];
}
}
return dp[3];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming