Maximum Score from Performing Multiplication Operations Solution
Maximum Score from Performing Multiplication Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Score from Performing Multiplication Operations is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- 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 nums of length n and multipliers of length m, with m <= n. Starting from a score of 0, perform exactly m operations; in the i-th operation (0-indexed):
- remove one element
xfrom either end ofnums(the first or the last remaining element), and - add
multipliers[i] * xto the score.
Return the maximum score reachable after all m operations.
Example 1
Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: Take 3, 2, 1 from the right: 9 + 4 + 1.
Example 2
Input: nums = [4,-2,5], multipliers = [2,-1]
Output: 12
Explanation: Take 5 (+10), then -2 from the right (+2).
Example 3
Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Constraints
n == nums.lengthm == multipliers.length1 <= m <= 300m <= n <= 10^5-1000 <= nums[i], multipliers[i] <= 1000
Hints for Maximum Score from Performing Multiplication Operations
Hint 1
Greedy choices fail — a big product now can leave terrible elements for later.
Hint 2
After
ioperations, ifleftof them took from the front, the remaining array is fixed: it starts atleftand ends atn - 1 - (i - left).Hint 3
So the state is
(i, left)— onlyO(m²)states, even thoughnis large. Take the better of front and back at each state.
How to solve Maximum Score from Performing Multiplication Operations
The removed elements always form a prefix and a suffix of nums. After i operations with left taken from the front, the right pointer is n - 1 - (i - left), so (i, left) describes the state completely and there are only about m²/2 of them.
Approach
- Let
dp[i][left]be the best score obtainable from operationsi..m-1whenleftelements have been taken from the front. dp[m][*] = 0.- For
ifromm-1down to 0 andleftfrom 0 toi: withright = n - 1 - (i - left),dp[i][left] = max(multipliers[i]·nums[left] + dp[i+1][left+1], multipliers[i]·nums[right] + dp[i+1][left]). - Return
dp[0][0]; a single row of sizem + 1suffices ifleftis processed in increasing order.
Why it works
Every play sequence is a sequence of front/back choices, and its future depends only on how many of each were made — exactly (i, left). The recurrence tries both choices and adds the optimal continuation, so it equals the best total over all sequences.
Complexity
- Time —
O(m²) - Space —
O(m)
Pitfalls
- Indexing the DP by both ends (
O(n²)) is too slow and too large whenn = 10^5; index by operations and front-count instead. - Values are negative too, so initialise maxima carefully (no 0 floor).
- The answer is at most
300 · 10^6, which fits in 32 bits.
Reference solution
Python
from typing import List
def maximumScore(nums: List[int], multipliers: List[int]) -> int:
n, m = len(nums), len(multipliers)
dp = [0] * (m + 1)
for i in range(m - 1, -1, -1):
mu = multipliers[i]
for left in range(i + 1):
right = n - 1 - (i - left)
a = mu * nums[left] + dp[left + 1]
b = mu * nums[right] + dp[left]
dp[left] = a if a > b else b
return dp[0]Java
public static int maximumScore(int[] nums, int[] multipliers) {
int n = nums.length, m = multipliers.length;
int[] dp = new int[m + 1];
for (int i = m - 1; i >= 0; i--) {
int mu = multipliers[i];
for (int left = 0; left <= i; left++) {
int right = n - 1 - (i - left);
int a = mu * nums[left] + dp[left + 1];
int b = mu * nums[right] + dp[left];
dp[left] = Math.max(a, b);
}
}
return dp[0];
}C++
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int n = nums.size(), m = multipliers.size();
vector<int> dp(m + 1, 0);
for (int i = m - 1; i >= 0; i--) {
int mu = multipliers[i];
for (int left = 0; left <= i; left++) {
int right = n - 1 - (i - left);
int a = mu * nums[left] + dp[left + 1];
int b = mu * nums[right] + dp[left];
dp[left] = max(a, b);
}
}
return dp[0];
}JavaScript
var maximumScore = function(nums, multipliers) {
var n = nums.length, m = multipliers.length;
var dp = new Array(m + 1).fill(0);
for (var i = m - 1; i >= 0; i--) {
var mu = multipliers[i];
for (var left = 0; left <= i; left++) {
var right = n - 1 - (i - left);
var a = mu * nums[left] + dp[left + 1];
var b = mu * nums[right] + dp[left];
dp[left] = a > b ? a : b;
}
}
return dp[0];
};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