Skip to main content
Talentd

Maximum Multiplication Score - Solution & Explanation

MediumArrayDynamic Programming20 min read
Practice this problem

Problem Statement

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 == 4
  • 4 <= 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.

Explanation:

The solution initializes a DP table where dp[i][j] represents the maximum score achievable using the first i+1 elements from array a and up to the j-th index of array b. Starting with the base case of using just one element from a, the code iteratively builds up to using all four elements, updating the table to reflect the best scores possible with overlapping subproblems.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity:

O(n) where n is the length of array b.

Space Complexity:

O(n) for storing the DP table for each element of a.

Try this approach in the editor →

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.

Explanation:

The C version addresses the recursive nature of the backtracking by rediscovering states through branches: 'including' versus 'excluding'. Terminology reflects moving through each aIndex and the equivalent path choices starting from bIndex.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity:

O(bLen^4) due to recursive exploration for each deployment path.

Space Complexity:

O(1) beyond recursion stack consumption, as backtracking is largely state-free other than call paths.

Try this approach in the editor →

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 array b has been completely traversed. At this point, if array a has also been completely traversed, return 0; otherwise, return negative infinity.
  • If i geq len(a), it means array a has been completely traversed. Return 0.
  • Otherwise, we can either skip the j-th element of array b and move to the next element, i.e., dfs(i, j + 1); or we can choose the j-th element of array b, in which case the score is a[i] times b[j] plus dfs(i + 1, j + 1). We take the maximum of these two values as the return value of dfs(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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity:

O(n) where n is the length of array b.

Space Complexity:

O(n) for storing the DP table for each element of a.

Backtracking Approach

Time Complexity:

O(bLen^4) due to recursive exploration for each deployment path.

Space Complexity:

O(1) beyond recursion stack consumption, as backtracking is largely state-free other than call paths.

Memoization—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking EnumerationO(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

Video Solution

3290. Maximum Multiplication Score (Leetcode Medium) • Programming Live with Larry • 893 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Multiplication Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays