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] <= 105Problem 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.
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.
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.
O(n) where n is the length of array b.
O(n) for storing the DP table for each element of a.
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.
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.
O(bLen^4) due to recursive exploration for each deployment path.
O(1) beyond recursion stack consumption, as backtracking is largely state-free other than call paths.
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:
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.i geq len(a), it means array a has been completely traversed. Return 0.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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity:
Space Complexity:
|
| Backtracking Approach | Time Complexity:
Space Complexity:
|
| Memoization | — |
| 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 |
3290. Maximum Multiplication Score (Leetcode Medium) • Programming Live with Larry • 878 views views
Watch 9 more video solutions →Practice Maximum Multiplication Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor