Maximum Multiplication Score solution and explanation
9 more videos on this problem
3290. Maximum Multiplication Score (Leetcode Medium)Programming Live with Larry · 6:07 · 893 views
3290 Maximum Multiplication Score || How to 🤔 in Interview || DP + Memoization 🔥Ayush Rao · 8:54 · 824 views
3290. Maximum Multiplication Score | Leetcode | Weekly Contest 415 | DPDev · 12:15 · 268 views
Maximum Multiplication Score | LeetCode 3290 | Leetcode Weekly Contest - 415Developer Coder · 34:30 · 209 views
Leetcode 3290 | Maximum Multiplication Score | Weekly Contest 415Road To FAANG · 8:26 · 180 views
Leetcode Weekly Contest 415 | 3290. Maximum Multiplication Score | RecursionCodeFod · 13:37 · 135 views
3290. Maximum Multiplication ScoreLeetcode and Interview Question · 10:52 · 127 views
Leetcode 3290 | Maximum Multiplication Score | Weekly Contest 415 | Medium | Solution in C++Shekhar Gupta · 10:39 · 78 views
Leetcode | Weekly Contest 415 | 3290. Maximum Multiplication Score | SolutionCode Wanderer · 7:23 · 24 views
Leetcode Weekly Contest 415 Solution |Two Sneaky Numbers of Digitville | Maximum Multiplication ScorThe CodeBreakz Show · 25:35 · 81 views
The problem
You are given an integer array a of size 4 and another integer array b of size at least 4.
You need to choose 4 indices i0, i1, i2, and i3 from the array b such that i0 < i1 < i2 < i3. Your score will be equal to the value a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].
Return the maximum score you can achieve.
Example 1:
Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
Output: 26
Explanation:
We can choose the indices 0, 1, 2, and 5. The score will be 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26.
Example 2:
Input: a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
Output: -1
Explanation:
We can choose the indices 0, 1, 3, and 4. The score will be (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1.
Constraints:
a.length == 44 <= b.length <= 105-105 <= a[i], b[i] <= 105
Approach overview
Problem Overview: You are given two arrays where one array contains four coefficients and the other contains many values. The task is to choose four increasing indices from the larger array and maximize the total score a[0]*b[i1] + a[1]*b[i2] + a[2]*b[i3] + a[3]*b[i4]. Order must be preserved, so once an index is chosen the next must come after it.
Approach 1: Backtracking Enumeration (Exponential Time)
This approach explores every possible combination of four indices from the second array while maintaining increasing order. A recursive function decides whether to include the current index or skip it. Once four elements are chosen, compute the multiplication score and update the maximum. This brute force technique directly models the problem but examines all combinations, leading to O(n^4) time complexity and O(4) recursion stack space. It works only for very small inputs and mainly helps you understand the structure of the decision tree.
Approach 2: Dynamic Programming (Optimal, O(n))
The key observation: you only need to know the best score after selecting the first k multipliers while scanning the second array from left to right. Define a DP state where dp[k] represents the maximum score after selecting k elements so far. For each value in the second array, update states in reverse order: compute potential contributions for the 4th, 3rd, 2nd, and 1st selections using a[k] * b[i]. Updating backward prevents overwriting states needed for the same iteration. This converts the combinational search into a linear scan with constant states.
The algorithm iterates through the array once and updates four DP states per element. That gives O(n) time complexity and O(1) space. This technique is a classic pattern in dynamic programming: compressing a multi-step decision process into rolling states. The ordered selection constraint is handled naturally because the scan moves left to right through the array. Conceptually, it resembles subsequence DP problems where each step extends the best partial solution.
Recommended for interviews: Start by explaining the brute-force combination idea to demonstrate understanding of the ordered selection constraint. Then transition to the dynamic programming optimization that tracks the best score for each selection stage. Interviewers typically expect the O(n) DP solution with constant space because it shows familiarity with subsequence-style DP state compression.
Approach 1: Dynamic Programming Approach
This approach utilizes dynamic programming to store intermediate solutions and avoid recalculating when possible. By progressively building up the solution, it ensures an efficient calculation of the maximum score.
def maxScore(a, b):
n = len(b)
dp = [[float('-inf')] * n for _ in range(4)]
for i in range(4):
for j in range(i, n):
if i == 0:
dp[i][j] = a[i] * b[j]
else:
maxPrev = max(dp[i-1][i-1:j])
dp[i][j] = maxPrev + a[i] * b[j]
return max(dp[3][3:])
if __name__ == "__main__":
a = [3, 2, 5, 6]
b = [2, -6, 4, -5, -3, 2, -7]
print("Maximum Score:", maxScore(a, b))import java.util.Arrays;
public class MaxScore {
public static int maxScore(int[] a, int[] b) {
int n = b.length;
int[][] dp = new int[4][n];
for (int i = 0; i < 4; i++) {
for (int j = i; j < n; j++) {
if (i == 0) {
dp[i][j] = a[i] * b[j];
} else {
int maxPrev = Integer.MIN_VALUE;
for (int k = i - 1; k < j; k++) {
maxPrev = Math.max(maxPrev, dp[i - 1][k]);
}
dp[i][j] = maxPrev + a[i] * b[j];
}
}
}
return Arrays.stream(dp[3]).skip(3).max().orElse(Integer.MIN_VALUE);
}
public static void main(String[] args) {
int[] a = {3, 2, 5, 6};
int[] b = {2, -6, 4, -5, -3, 2, -7};
System.out.println("Maximum Score: " + maxScore(a, b));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
int maxScore(const std::vector<int>& a, const std::vector<int>& b) {
int n = b.size();
std::vector<std::vector<int>> dp(4, std::vector<int>(n, INT_MIN));
for (int i = 0; i < 4; ++i) {
for (int j = i; j < n; ++j) {
if (i == 0) {
dp[i][j] = a[i] * b[j];
} else {
int maxPrev = INT_MIN;
for (int k = i - 1; k < j; ++k) {
maxPrev = std::max(maxPrev, dp[i - 1][k]);
}
dp[i][j] = maxPrev + a[i] * b[j];
}
}
}
return *std::max_element(dp[3].begin() + 3, dp[3].end());
}
int main() {
std::vector<int> a = {3, 2, 5, 6};
std::vector<int> b = {2, -6, 4, -5, -3, 2, -7};
std::cout << "Maximum Score: " << maxScore(a, b) << std::endl;
return 0;
}function maxScore(a, b) {
const n = b.length;
const dp = Array.from({ length: 4 }, () => Array(n).fill(-Infinity));
for (let i = 0; i < 4; i++) {
for (let j = i; j < n; j++) {
if (i === 0) {
dp[i][j] = a[i] * b[j];
} else {
let maxPrev = -Infinity;
for (let k = i - 1; k < j; k++) {
maxPrev = Math.max(maxPrev, dp[i - 1][k]);
}
dp[i][j] = maxPrev + a[i] * b[j];
}
}
}
return Math.max(...dp[3].slice(3));
}
const a = [3, 2, 5, 6];
const b = [2, -6, 4, -5, -3, 2, -7];
console.log("Maximum Score:", maxScore(a, b));#include <stdio.h>
#include <limits.h>
int maxScore(int a[], int b[], int n) {
int dp[4][n];
for (int i = 0; i < 4; ++i)
for (int j = 0; j < n; ++j)
dp[i][j] = (i == 0 ? a[i] * b[j] : INT_MIN);
for (int i = 1; i < 4; ++i) {
int maxPrev = INT_MIN;
for (int j = i; j < n; ++j) {
maxPrev = (maxPrev > dp[i-1][j-1]) ? maxPrev : dp[i-1][j-1];
dp[i][j] = maxPrev + a[i] * b[j];
}
}
int maxScore = INT_MIN;
for (int j = 3; j < n; ++j)
maxScore = (maxScore > dp[3][j]) ? maxScore : dp[3][j];
return maxScore;
}
int main() {
int a[] = {3,2,5,6};
int b[] = {2,-6,4,-5,-3,2,-7};
int n = sizeof(b) / sizeof(b[0]);
int score = maxScore(a, b, n);
printf("Maximum Score: %d\n", score);
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxScore(int[] a, int[] b) {
int n = b.Length;
int[,] dp = new int[4, n];
for (int i = 0; i < 4; i++)
for (int j = i; j < n; j++)
dp[i, j] = int.MinValue;
for (int i = 0; i < 4; i++) {
for (int j = i; j < n; j++) {
if (i == 0) {
dp[i, j] = a[i] * b[j];
} else {
int maxPrev = int.MinValue;
for (int k = i - 1; k < j; k++)
maxPrev = Math.Max(maxPrev, dp[i - 1, k]);
dp[i, j] = maxPrev + a[i] * b[j];
}
}
}
return Enumerable.Range(3, n-3).Select(j => dp[3, j]).Max();
}
public static void Main(string[] args) {
int[] a = {3, 2, 5, 6};
int[] b = {2, -6, 4, -5, -3, 2, -7};
Solution solution = new Solution();
Console.WriteLine("Maximum Score: " + solution.MaxScore(a, b));
}
}Explanation:
The provided Python code follows the established logic of storing interim results in a DP table. It efficiently calculates the cumulative score for index choices, iterating over all combinations while ensuring optimization with prev steps.
Time Complexity:
O(n^2) given that it processes each possible combination explicitly.
Space Complexity:
O(n) conflicting memory usage for storing the DP state table.
Approach 2: Backtracking Approach
The backtracking approach attempts to explore the solution space by choosing indices for array 'b' step-by-step, pruning paths that don't yield higher scores. This recursive solution is important to recognize but may have practical limitations compared to dynamic programming.
def maxScore(a, b):
def maxScoreRec(a, b, aIndex, bIndex, score):
if aIndex == len(a):
return score
if bIndex == len(b):
return 0
include = maxScoreRec(a, b, aIndex+1, bIndex+1, score + a[aIndex] * b[bIndex])
exclude = maxScoreRec(a, b, aIndex, bIndex+1, score)
return max(include, exclude)
return maxScoreRec(a, b, 0, 0, 0)
if __name__ == "__main__":
a = [3, 2, 5, 6]
b = [2, -6, 4, -5, -3, 2, -7]
print("Maximum Score:", maxScore(a, b))public class MaxScoreBacktrack {
public static int maxScore(int[] a, int[] b) {
return maxScoreHelper(a, b, 0, 0, 0);
}
private static int maxScoreHelper(int[] a, int[] b, int aIndex, int bIndex, int score) {
if (aIndex == a.length) return score;
if (bIndex == b.length) return 0;
int include = maxScoreHelper(a, b, aIndex+1, bIndex+1, score + a[aIndex]*b[bIndex]);
int exclude = maxScoreHelper(a, b, aIndex, bIndex+1, score);
return Math.max(include, exclude);
}
public static void main(String[] args) {
int[] a = {3, 2, 5, 6};
int[] b = {2, -6, 4, -5, -3, 2, -7};
System.out.println("Maximum Score: " + maxScore(a, b));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxScoreRec(const std::vector<int>& a, const std::vector<int>& b, int aIndex, int bIndex, int score) {
if (aIndex == a.size()) return score;
if (bIndex == b.size()) return 0;
int include = maxScoreRec(a, b, aIndex + 1, bIndex + 1, score + a[aIndex] * b[bIndex]);
int exclude = maxScoreRec(a, b, aIndex, bIndex + 1, score);
return std::max(include, exclude);
}
int maxScore(const std::vector<int>& a, const std::vector<int>& b) {
return maxScoreRec(a, b, 0, 0, 0);
}
int main() {
std::vector<int> a = {3, 2, 5, 6};
std::vector<int> b = {2, -6, 4, -5, -3, 2, -7};
std::cout << "Maximum Score: " << maxScore(a, b) << std::endl;
return 0;
}function maxScore(a, b) {
function maxScoreRec(aIdx, bIdx, score) {
if (aIdx === a.length) return score;
if (bIdx === b.length) return 0;
const include = maxScoreRec(aIdx + 1, bIdx + 1, score + a[aIdx] * b[bIdx]);
const exclude = maxScoreRec(aIdx, bIdx + 1, score);
return Math.max(include, exclude);
}
return maxScoreRec(0, 0, 0);
}
const a = [3, 2, 5, 6];
const b = [2, -6, 4, -5, -3, 2, -7];
console.log("Maximum Score:", maxScore(a, b));#include <stdio.h>
int maxScoreRec(int a[], int b[], int aLen, int bLen, int aIndex, int bIndex, int score) {
if (aIndex == aLen) return score;
if (bIndex == bLen) return 0;
int include = maxScoreRec(a, b, aLen, bLen, aIndex + 1, bIndex + 1, score + a[aIndex] * b[bIndex]);
int exclude = maxScoreRec(a, b, aLen, bLen, aIndex, bIndex + 1, score);
return include > exclude ? include : exclude;
}
int maxScore(int a[], int b[], int bLen) {
return maxScoreRec(a, b, 4, bLen, 0, 0, 0);
}
int main() {
int a[] = {3, 2, 5, 6};
int b[] = {2, -6, 4, -5, -3, 2, -7};
printf("Maximum Score: %d\n", maxScore(a, b, 7));
return 0;
}using System;
public class Solution {
public int MaxScore(int[] a, int[] b) {
return MaxScoreHelper(a, b, 0, 0, 0);
}
private int MaxScoreHelper(int[] a, int[] b, int aIdx, int bIdx, int score) {
if (aIdx == a.Length) return score;
if (bIdx == b.Length) return 0;
int include = MaxScoreHelper(a, b, aIdx + 1, bIdx + 1, score + a[aIdx] * b[bIdx]);
int exclude = MaxScoreHelper(a, b, aIdx, bIdx + 1, score);
return Math.Max(include, exclude);
}
public static void Main() {
int[] a = {3, 2, 5, 6};
int[] b = {2, -6, 4, -5, -3, 2, -7};
Solution solution = new Solution();
Console.WriteLine("Maximum Score: " + solution.MaxScore(a, b));
}
}Explanation:
Python's backtracking solution applies a series of recursive decisions representing potential paths, calculating through which steps lead to the peak score possibilities while iterating potential combinations.
Time Complexity:
O(bLen^4) Because each combination permutation calls for evaluation.
Space Complexity:
O(1) is unaffected beyond stack depth from recursion.
Approach 3: Memoization
We design a function dfs(i, j), which represents the maximum score that can be obtained starting from the i-th element of array a and the j-th element of array b. Then the answer is dfs(0, 0).
The function dfs(i, j) is calculated as follows:
- If
j geq len(b), it means arraybhas been completely traversed. At this point, if arrayahas also been completely traversed, return0; otherwise, return negative infinity. - If
i geq len(a), it means arrayahas been completely traversed. Return0. - Otherwise, we can either skip the
j-th element of arrayband move to the next element, i.e.,dfs(i, j + 1); or we can choose thej-th element of arrayb, in which case the score isa[i] times b[j]plusdfs(i + 1, j + 1). We take the maximum of these two values as the return value ofdfs(i, j).
We can use memoization to avoid redundant calculations.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of arrays a and b, respectively.
function maxScore(a: number[], b: number[]): number {
const [m, n] = [a.length, b.length];
const f: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
const dfs = (i: number, j: number): number => {
if (j >= n) {
return i >= m ? 0 : -Infinity;
}
if (i >= m) {
return 0;
}
if (f[i][j] !== -1) {
return f[i][j];
}
return (f[i][j] = Math.max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1)));
};
return dfs(0, 0);
}func maxScore(a []int, b []int) int64 {
m, n := len(a), len(b)
f := make([][]int64, m)
for i := range f {
f[i] = make([]int64, n)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int64
dfs = func(i, j int) int64 {
if j >= n {
if i >= m {
return 0
}
return math.MinInt64 / 2
}
if i >= m {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
f[i][j] = max(dfs(i, j+1), int64(a[i])*int64(b[j])+dfs(i+1, j+1))
return f[i][j]
}
return dfs(0, 0)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity:
Space Complexity:
|
| Backtracking Approach | Time Complexity:
Space Complexity:
|
| Memoization | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(n^4) | O(4) | Conceptual baseline to understand the ordered combination structure |
| Dynamic Programming (State Compression) | O(n) | O(1) | Optimal solution for large inputs and typical interview expectations |
Frequently asked questions
Is Maximum Multiplication Score easy or hard?
Maximum Multiplication Score is considered a Medium difficulty problem. The brute-force idea is straightforward, but recognizing the dynamic programming optimization and compressing the state into constant space requires familiarity with subsequence DP patterns.
Maximum Multiplication Score Python/Java solution
Python and Java implementations typically maintain a DP array of length four and update it while iterating through the second array. Each step calculates candidate scores using the given multipliers and keeps the maximum value, achieving O(n) time complexity.
How to solve Maximum Multiplication Score in O(n)?
Maintain four DP values representing the best score after selecting 1, 2, 3, and 4 elements. Iterate through the array and update dp[4], dp[3], dp[2], and dp[1] in reverse order using the formula dp[k] = max(dp[k], dp[k-1] + a[k-1] * b[i]). This ensures correct ordering while computing the optimal score in a single pass.
What is the best approach for Maximum Multiplication Score?
The optimal solution uses dynamic programming with four states representing how many multipliers have been chosen so far. While scanning the second array, update these states in reverse order to compute the best score. This reduces the search space from combinations to a linear scan with O(n) time and O(1) space.
Is Maximum Multiplication Score asked at Google/Amazon/Meta?
Problems with subsequence dynamic programming and weighted selection patterns appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test DP state transitions, array traversal, and optimization from brute force to linear-time solutions.
What data structure is used in Maximum Multiplication Score?
The solution primarily uses arrays and dynamic programming states. A small DP array of size four tracks the best multiplication score for each stage of element selection while iterating through the input array.
What is the time complexity of Maximum Multiplication Score?
The optimal dynamic programming approach runs in O(n) time because the algorithm scans the array once and performs a constant number of updates per element. Space complexity is O(1) since only four DP states are maintained.